도미노 밀어 증명하기
초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
반복문이 맞게 도는지 따질 때 백 바퀴를 다 따라가 보지는 않습니다. 처음에 맞는지, 그리고 한 바퀴 돌아도 맞는 상태가 이어지는지를 봅니다. 이 두 가지만으로 몇 바퀴를 돌든 맞다고 할 수 있는 까닭을 알아봅시다.
줄지어 세운 도미노는 다음 두 가지만 확인하면 끝없이 길어도 모두 넘어진다고 장담할 수 있습니다.
명제도 같습니다. n = 1일 때 참임을 보이는 것이 1번, 기초 단계(base case)입니다. n = k일 때 참이면 n = k + 1일 때도 참임을 보이는 것이 2번, 귀납 단계(inductive step)입니다. 둘을 보이면 모든 n에 대해 참입니다. 이 방법을 수학적 귀납법(mathematical induction)이라 합니다.
칸이 n개인 배열 nums에서 가장 큰 수를 찾는 다음 반복문이 있다고 합시다.
int biggest = nums[0];
int i = 1;
while (i < n) {
if (nums[i] > biggest) {
biggest = nums[i];
}
i = i + 1;
}
배열이 몇 칸이든 끝나면 biggest가 가장 큰 수일까요? 증명할 명제는 다음과
같습니다.
앞 k칸을 본 뒤 biggest는 그중 가장 큰 수다
biggest = nums[0] = 14
다음을 눌러 한 칸씩 넓혀 봅시다.
기초 단계. 반복문에 들어가기 전 biggest는 nums[0]입니다. 앞 1칸에서 가장
큰 수는 그 칸의 값이니 맞습니다.
귀납 단계. 앞 k칸을 본 뒤 biggest가 그중 가장 큰 수라고 합시다. 다음
바퀴는 k + 1번째 칸 nums[k]와 biggest를 비교해 큰 쪽을 남깁니다. 앞 k칸에서
가장 큰 수와 새 칸 중 큰 쪽이니, 앞 k + 1칸에서 가장 큰 수입니다.
수학적 귀납법에 따라 명제는 모든 k에 대해 참입니다. 반복문이 끝나면 모든 칸을 본
것이니 biggest는 배열 전체에서 가장 큰 수입니다.
“앞 k칸을 본 뒤 biggest는 그중 가장 큰 수”처럼 반복문이 한 바퀴 돌 때마다 늘 참으로 남는 성질을 반복문 불변식(loop invariant)이라 합니다. 반복문에 들어갈 때 참이고 한 바퀴 돌아도 참으로 남으면, 끝났을 때도 참입니다. 앞의 것이 기초 단계, 뒤의 것이 귀납 단계입니다. 반복문이 맞다는 것은 이렇게 불변식을 세워 증명합니다.
다음 증명은 틀렸습니다. 기초 단계는 맞고, 귀납 단계는 어떤 k 하나에서만 성립하지 않습니다. 그 k는 무엇일까요? 숫자로 답하세요.
명제: 공 n개를 모으면 언제나 모두 같은 색이다. 기초 단계: n = 1이면 공이 하나뿐이니 참이다. 귀납 단계: 공 k개는 언제나 같은 색이라고 하자. 공 k + 1개를 한 줄로 놓는다. 맨 뒤 공을 빼면 k개이니 모두 같은 색이다. 맨 앞 공을 빼도 k개이니 모두 같은 색이다. 두 무리에 함께 든 공이 있으니 k + 1개가 모두 같은 색이다.