알고리즘을 공부하다보면, 알고리즘적 사고를 공부하게됩니다. 코드를 구성하는 것도 중요하지만 논리적으로 내 코드가 참임을 증명할 수 있어야 합니다. 그리고 6.006을 듣다보면 가장 많이 나오는 말이 귀납법입니다.
귀납법은 음이 아닌 정수 n에 대해, 어떤 명제P(n)이 참임을 증명하는 방법입니다. 비유하자면 첫 번째 도미노(P(0))가 쓰러지고 세워져 있는 도미노 중 어떤 도미노가 쓰러지고 그 다음 도미노가 쓰러진다는 것이 보장(P(n)=>P(n+1))된다면, 결국 모든 도미노가 쓰러지게 된다는 원리입니다.
귀납법의 수행 방법 (5단계 탬플릿)
해당 수업에서는 5단계 탬플릿을 기반으로 귀납법을 수행할 것을 권장합니다. 귀납법을 수행하는 사람이나, 그리고 그것을 읽는 사람 모두 편하게 하는 방법을 제안했다고 보시면 되겠습니다.
1. 귀납법 사용 명시 : 귀납법을 사용함을 밝혀 읽는 사람이 앞으로 귀납법을 수행 할 것을 알도록 합니다
2. 명제 정의(Predicate) : 증명하려는 명제 P(n)을 정의 하니다. 아직 참인게 밝혀진게 아니니, 귀납 가설(Induction Hypothesis)라고 정의합니다. 우리가 잘 아는 등차수열의 합을 기준으로 하면 P(n) = 1 + 2 + 3 + ... + n = n(n+1)/2 라고 가정합니다.
3. 기초 단계(Base case): 가장 작은 값의 참을 증명합니다. n=0 또는 n=1인 경우를 증명합니다. 가령, 앞의 등차수열을 그대로 가져가면 P(0) = 0 임을 증명할 수 있습니다. P(1)=1도 마찬가지 입니다.
4. 귀납 단계 (Inductive Step) : 모든 n>=0에 대하여 P(n)이 참이라고 가정할 때, P(n+1)도 참이다를 증명합니다. 가령 등차수열로 다시 간다면
4.1. P(n)이 참이라 가정. 1 + ... + n = n(n+1)/2
4.2. P(n)에 다음 단계인 n+1을 더해봅니다. 1 + ... + n + (n+1) = n(n+1)/2 + (n+1)
