지나가던 개발자
[Algorithm] 1부터 n까지의 합이 {n(n+1)}/2인 이유 본문
저번에 백준의 8393번 문제를 풀며 이 공식에 관한 이야기를 잠시 했다.
오늘 그 이유를 증명해보고자 한다.
시작하기 앞서, 이 공식은 고등학교 수학I의 수열 단원에 나오며, 그 이름도 유명한 가우스가 사용했던 공식이라고 한다.
우선 공차가 1인 등차수열 A가 있다고 생각해보자. 첫째항이 a, 공차가 d인 등차수열의 일반항은 An = a + (n - 1)d 이므로, An = n 이다.
그렇다면 1부터 n까지의 이 수열은 {1, 2, 3, 4, 5, 6, 7, 8, ... , n-3, n-2, n-1, n} 이 될 것이다. 그렇다면 1부터 n까지의 합을 구하려면, 1부터 n까지 직접 더하는 방법이 있다. 그렇지만 이 방법은 너무나 비효율적이다.
s = 0
n = int(input())
for i in range(1, n+1):
s += i
print(s)
이런식으로 더할 수 있다고는 하지만, 만약 10,000,000,000,000정도 되는 큰 숫자가 나온다면 컴퓨터라 하더라도 연산에 오랜 시간이 걸릴 것이다.
그렇다면 이런 방법을 써 보자.
1에서 n까지의 수열을 한번 뒤집어보자. 뒤집은 뒤에 더해도 어처피 합은 똑같으니. 뒤집으면 {n, n-1, n-2, n-3, ... , 3, 2, 1}과 같은 수열이 나올 것이다.
그러면 원래 있던 수열과 뒤집은 수열을 한번 더해보자.
{1, 2, 3, ... , n-2, n-1, n}
+
{n, n-1, n-2, ... , 3, 2, 1}
n+1, n+1, n+1, n+1, ...
놀랍게도 n+1만 계속 반복된다. 계속이 아니라 n번 반복된다. 그런데 n+1을 n번 더한다면 (1부터 n까지의 합)*2의 값이 될 것이다. 당연하게도 수열 두개를 더했으니. 따라서 {n(n+1)}/2으로 해줘야 한다. 이렇게 되니 우리가 맨 처음 증명하려 했던 식이 나왔다.
그렇다면 이번에는 공차가 2인 수열로 한번 해보자.
{2, 4, 6, ... , n-4, n-2, n}
+
{n, n-2, n-4, ... , 6, 4, 2}
n+2, n+2, n+2, n+2 ...
이번에는 n+2만 계속 반복된다. 그렇게 되면 {n(n+2)}/2라는 식으로 계산하면 2부터 n까지 이어지는 공차가 2인 등차수열의 합을 구할 수 있겠다.
그렇다면 이번에는 마지막으로, a를 첫째항, l을 제n항, 공차를 d로 갖는 수열 Sn으로 다시 한번 해보자.
{a, (a+d), (a+2d), ... , (l-2d), (l-d), l}
+
{l, (l-d), (l-2d), ... , (a+2d), (a+d), a}
a+l, a+l, a+l, a+l ...
이번에는 a+l만 계속 반복된다. 그렇다면 a부터 l까지의 합은 {n(a+l)}/2로 나타낼 수 있을 것이다. 그런데 여기서 제n항 l은 a+(n-1)d 로 나타낼 수 있다. 첫째항 a에다가 공차 d를 n-1번 더한 것이라는 말이다. 왜 d를 n-1번 더하냐는 의문이 들 수도 있다. 그 이유는 a가 첫째항이기 때문이다. 제2항부터 n을 더하는데 a = S₁이니까, 결국 제n항 l은 a+(n-1)d가 되는 것이다.
그렇다면 {n(a+l)}/2를 이렇게 나타낼 수 있겠다. n{a+a+(n-1)d}/2. 그럼 이걸 정리하면 n{2a+(n-1)d}/2가 된다.
따라서, a를 첫째항, 공차를 d로 갖는 등차수열 Sn에서 a부터 l까지의 합은,
n{2a+(n-1)d}/2
이다.
그렇다면 공차가 1, 첫째항이 1인 등차수열 An에서는
n{2+(n-1)1}/2 = {n(n+1)}/2
가 되는 것이다.
그렇다면 이대로 코드를 한번 짜보고 원래 반복문을 사용했던 코드와 시간 복잡도를 비교하여 보자.
n = int(input())
print(n*(n+1)//2)
1부터 1,000,000까지를 한번 더해 보았다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
![](https://blog.kakaocdn.net/dn/B4f75/btrq12YCJQj/5qkQQ1FSru8hJlv7311tW1/img.jpg)
0.3초가 넘게 걸리던 코드를 0.00008초만에 해결할 수 있게 바꾸었다.
'Algorithm' 카테고리의 다른 글
[Algorithm] 비트마스킹 | Python (0) | 2022.12.02 |
---|---|
[Algorithm] 분할 정복을 이용한 거듭제곱 | 빠른 거듭제곱 | Python (0) | 2022.10.22 |
[Algorithm] 오일러 피 함수(Euler's phi function) | 서로소인 자연수의 개수 구하기 | Python (1) | 2022.10.22 |
[Algorithm] 카라추바 알고리즘 | 빠른 곱셈 | Python (1) | 2022.09.09 |
[Algorithm] 빅오(Big-O) 표기법으로 시간 복잡도 나타내기 (0) | 2022.08.29 |