yeolyi.com성열의 컴퓨터공학

도미노 밀어 증명하기

수학적 귀납법

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

반복문이 맞게 도는지 따질 때 백 바퀴를 다 따라가 보지는 않습니다. 처음에 맞는지, 그리고 한 바퀴 돌아도 맞는 상태가 이어지는지를 봅니다. 이 두 가지만으로 몇 바퀴를 돌든 맞다고 할 수 있는 까닭을 알아봅시다.

도미노

줄지어 세운 도미노는 다음 두 가지만 확인하면 끝없이 길어도 모두 넘어진다고 장담할 수 있습니다.

  1. 첫 번째 도미노가 넘어진다.
  2. 어떤 도미노든 넘어지면 바로 다음 도미노도 넘어진다.

명제도 같습니다. 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는 그중 가장 큰 수다

nums 앞 1칸
1432783521

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개가 모두 같은 색이다.