가우스 공식

코딩 이론 2023. 5. 3. 13:37

오늘 프로그래머스를 푸는데 나는 반복문을 사용하여 풀었지만 다른 사람은 반복문을 사용하지 않고 가우스 공식을 사용하여 푸는 것을 보았다. 가우스 공식이 간간히 나오는 것을 보았고 이번엔 알아보기로 했다.

일반적으로 가우스 공식이라 말하지만 교육과정의 정식 명칭은 '등차수열의 합 공식' 이다.
- 등차수열은 뒤의 숫자와 앞의 숫자의 차가 모두 같은 수의 나열
배열이나 정수 목록과 같은 수열의 합을 빠르고 효율적을 계산할 수 있다.
반복문을 사용하지 않아 코드가 단순화 되고 효율적으로 코드를 작성할 수 있다.

원리

가우스 공식을 사용하려면 초기 값인 첫 항(a), 뒤의 숫자와 앞의 숫자의 차이인 항간의 공차(d), 항의 수(n)가 필요하다.

위의 기호를 사용하여 등차수열을 나타내면 a, a+d, a+2d, ···, a+(n-1)d가 된다.
1번의 등차수열을 거꾸로한 1번의 등차수열과 각 항을 더해주면 각 항이 모두 같은 값이 된다.(2a + (n-1)d, 2a + (n-1)d, 2a + (n-1)d, ···, 2a + (n-1)d)
2번에서 같은 값이 나온 항에 항의 갯수가 n개이므로 n을 곱해준다.((2a + (n-1)d) + (2a + (n-1)d) + ... + (2a + (n-1 )d)) = n(2a + (n-1)d)
3번의 값에 나누기 2를 해준다. => 2번에서 결과적으로 등차수열을 등차수열과 더한 것이 되므로 2배가 되어있는 상태이기 때문에 n(2a + (n-1)d) / 2

// 1부터 2씩 증가하는 10개의 요소를 가진 배열의 요소의 합을 구하여라.
// 첫 항의 값은 1,  공차는 2, 항의 갯수는 10

const result = (10/2)*(2*1+(10-1)*2) // 100