[수학과 프로그래밍] 1부터 N까지의 합

이 카테고리에서는 단순히 수학적 공식 혹은 지식을 깊게 다루진 않는다.
프로그래밍과 연관 지어서 유용하게 사용할 수 있는 수학적 지식을 다룬다.

---

1 + 2 + 3 + ... + n 의 결과는 무엇일까?

고등학교 교과과정에서 해당 식의 결과를 구하는 방법을 배웠다. 각 숫자의 나열을 수열이라 하고, 어떠한 규칙이냐에 따라 등차 혹은 등비로 나뉘었다. 해당 식의 경우 각 수열의 차가 1인 등차수열의 합이다.

해당 식은 간단하게 시그마(Σ)라는 기호를 사용하여 표현하였고, 시그마에 나오는 식의 종류나 형태에 따라 공식이 존재했다.

공식의 도출과정과 어떠한 형태로 코드에 나타날 수 있는지 프로그래머의 입장으로 다시 한번 식을 살펴보자.

---

먼저 공식의 도출 과정이다.
1 + 2 + 3 + ... + n을 나눠서 생각해보자,

만약 n이 짝수라면

첫째 숫자 1과 마지막 숫자 n 의 합 : n + 1
둘째 숫자 2와 마지막 전의 숫자 n-1의 합 : 2 + n - 1 = n + 1
셋째 숫자 3과 마지막 전전의 숫자 n-2 의 합 : 3 + n - 2 = n + 1
..

만약 n이 홀수라면

첫째 숫자를 0이라 하여 0과 마지막 숫자 n 의 합 : n
둘째 숫자 1와 마지막 전의 숫자 n-1의 합 : 1 + n - 1 = n
셋째 숫자 2과 마지막 전전의 숫자 n-2 의 합 : 2 + n - 2 = n
..

이런식으로 진행이 된다. 그렇다면

짝수일 때는 합이 n+1이 되는 쌍은 n/2개 나오고,
홀수일 때는 합이 n이 되는 쌍이 (n+1)/2 개 나온다

따라서 두 경우 모두 n(n+1)/2가 된다.

---

 

그렇다면 이러한 등차수열의 합은 프로그래밍에서 어떤 형태로 나타날까?

보통 중첩된 루프(nested loop)에서 이러한 형태를 많이 볼 수 있다.
예를 들어, 아래와 같은 코드의 시간 복잡도를 알아본다고 하자.

for(int i=0; i<n; i++){
	for(int j=i+1; j<n; j++){
    	// do something
    }
}

바깥쪽의 loop는 n번 도는게 자명하다.
안쪽의 loop는 어떤 식으로 동작할까?

i가 0일 때 n-1번
i가 1일 때 n-2번
i가 2일 때 n-3번
...
i가 n-1일 때 0번

이런 식으로 나아간다. 즉, 안쪽의 loop 순회는 등차수열의 공식에 따라 n(n-1)/2번이 수행된다고 볼 수 있고, 따라서 시간 복잡도는 O(n(n-1)/2) = O(n²)이다.