1부터 100까지 더하기 알고리즘 문제를 O(1) 시간으로 푸는 법 (가우스 법칙 원리)

코딩 테스트에서 가끔 1부터 숫자 n까지 더하라는 문제가 나온다.

 

총합 = 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n

 

 

예시: 숫자 n이 5일 경우

총합 = 1 + 2 + 3 + 4 + 5

 

위와 같이 반복문으로 풀면 되지만 문제점은 숫자 n이 커질수록 반복문 실행 숫자가 숫자 n만큼 동일하게 커진다.

즉, 이 알고리즘의 시간 복잡도는 O(n)이 된다.

 

하지만 가우스 법칙으로 이 문제를 O(1)으로 풀 수 있다.

 

가우스 법칙 공식은 아래와 같다.

총합 = (n+1)n / 2

 

 

아니 시8 이게 가능한가?라고 궁금증이 생기고 왜 저 공식이 가능한지 알아보자.

 

 

처음 보여준 공식을 두 개를 더해보자 (이때 두 번째 공식의 숫자 나열을 뒤집어보자, 어차피 뒤집어도 계산에 지장이 없지만

가우스 법칙을 증명할 때 필요하기 때문)

 

   총합 =  1 +      2     +      3      + ... + (n - 2) + (n - 1) + n

+ 총합 = n + (n - 1) + (n - 2) + ... +      3      +     2      + 1

=========================================

2 총합 = n + 1 + n + 1 + n + 1 ... (n + 1이 n만큼 반복한다 왜냐하면 두 공식의 덧셈이 1부터 n이기 때문)

 

2 총합 = (n + 1)n

 

2 총합 / 2 = (n + 1)n / 2

 

총합 = (n + 1)n / 2

 

그래서 가우스 법칙 공식이 총합 = (n + 1)n / 2 이다.