가우스 알고리즘
논리적 증명에서 비롯하는 프로그래밍의 기초
코딩과 영어의 학습원리는 일맥상통한다. 코딩 / 영어의 기본기는 논리적 사고 절차(기초수학 / 기초문법)이고, 기초체력은 자기 수준보다 조금 높은 소재(코딩에선 게임프로젝트 한 개, 영어에서는 통속소설 한 권)를 가지고 끊임없이 어떤 절차로 구현하는지(해석하는지) 연습하면 키울 수 있다는 거!
학교에서 선생님의 1부터 50까지의 합이 얼만지에 대한 질문에 단 번에 발상해냈다는 것으로 유명한 수학자 가우스에 대해 한 번쯤 들어봤을 법하다.
가우스는 1부터 100의 첫 번째 숫자 1과 맨 끝 숫자 100을 더한 값 101과 같은 수의 배열이 총 50개 있으므로 101 X 50 = 5050로 이끌어낸 수학식으로 증명했다(천재!).
똑같은 원리로 가우스 등식, n까지의 합을 덧셈, 곱셈, 나눗셈 각 1번씩만 써서 구할 수 있다.
누적합을 증가하는 순, 감소하는 순으로 각각 나열해보면 다음 두 등식을 얻는다.
sigma(n) = 1 + 2 +... + (n-1) + n
sigma(n) = n + (n-1) +... + 2 + 1
위의 두 등식에서 각 항의 아래와 위를 합하면 다음 등식이 성립하고,
sigma(n) = (n+1) + (n+1) + (n+1) + (n+1)
이 등식을 정리하면 다음 등식이 되고,
2 x sigma(n) = n x (n + 1)
양변을 2로 나누면,
sigma(n) = n x (n + 1) / 2
위의 덧셈, 곱셈, 나눗셈 각 1번씩만 쓴 등식을 사용하여 n까지의 자연수의 누적 합을 구하는 함수를 다음과 같이 간단히 구현할 수 있다(도경구, 2021).
def sigma(n):
return n * (n+1) // 2
위의 누적 합을 계산하는 가우스 알고리즘을 또한 참인지 아닌지를 검증해보자.
앞서 재귀라는 개념에서 자연수의 귀납 구조를 활용한 아래의 수학적 귀납법(mathematical induction)으로 모든 자연수에 대해서 이 알고리즘이 잘 작동하는지 검증할 수 있다(도경구, 2021).
- 수학적 귀납법(모든 자연수)
기초 단계(base) : P(0)은 참이다.
귀납 단계(induction) : 임의의 자연수 n에 대해서 P(n)이 참이면, P(n+1)도 참이다.
- 가우스 알고리즘 정리
임의의 자연수 n까지의 누적합 sigma(n)을 다른 식(가우스 등식)으로 계산함.
sigma(n) = n x (n + 1) / 2
- 증명(수학적 귀납)
기초 단계(base) : 0까지의 누적 합은 0이어여야 함. 위의 식에 0을 대입하면 0이므로 n이 0일 때 앞의 명제는 참임.
귀납 단계(induction) : 임의의 자연수 n에 대해서 n까지의 누적 합이 다음과 같다고 가정하자. - sigma(n) = n x (n + 1) / 2 (귀납 과정, induction hypothesis)
귀납 단계의 증명은 가우스 등식에 sigma(n+1)를 대입한 sigma(n ← n+1)
- sigma(n+1) = (n+1 x ((n+1) + 1)) / 2
이 등식이 귀납 가정을 활용하여 다음과 같이 유도해서 정리한 식과 동일한 지의 여부를 따진다.
귀납 정의 등식, sigma(n+1) = sigma(n) + n+1에서 우변의 n까지의 합, 즉 sigma(n)을 가우스의 등식(n까지의 합)으로 바꿈
sigma(n+1) = n x (n + 1) / 2 + n+1 ← 통분함.
sigma(n+1) = (n x (n+1) + 2(n+1)) / 2 ← 분자 정리함.
sigma(n+1) = (n+1)(n+2) / 2
정리한 식의 우변은 가우스 등식에 sigma(n+1)를 대입한 우변의 식 (n+1 x ((n+1) + 1)) / 2와 동일함.
기초 단계와 귀납 단계가 모두 참이므로, 수학적 귀납법에 의해서 가우스의 등식(알고리즘)은 참이다.
참조
1) 도경구 (2021). 제어 구조의 설계 원리를 중심으로 배우는 프로그래밍의 정석 파이썬.
