수학적 귀납법, 반복문 불변식

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음.

 

 

목차 (눌러서 이동)

 

수학적 귀납법

반복적인 구조를 갖는 명제의 증명에 유용하게 사용할 수 있다. 

 

먼저, 증명할 사실을 여러 단계로 나누고 그 중 첫 단계에서 증명이 성립함을 보인다. 어떤

한 단계에서 증명이 성립하면, 다음 단계에서도 성립함을 보인다. (단계 나누기 → 첫 단계

증명 → 귀납 증명)

 

사다리 게임을 예로 들어보자. N 개의 세로줄에 가로 줄을 원하는 만큼 그어도 위, 아래의

선택지가 1:1로 대응됨을 증명한다.

 

 1. 단계 나누기 : N 개의 세로 줄에 가로 줄을 하나씩 그어 간다. 가로 줄을 하나 긋는 것을

한 단계라고 하자.

 

 2. 첫 단계 증명 : 텅빈 N개의 세로 줄은 항상 위의 선택지와 아래의 선택지가 1:1 로 대응.

 

 3. 귀납 증명 : 가로 줄을 그어서 두 개의 세로 줄을 이으면 두 줄의 결과가 뒤바뀌고 전체

줄들의 1:1 대응 관계는 유지된다. 가로 줄을 그을 때마다 두 세로 줄의 결과가 뒤바뀐다.

반복문 불변식

대부분의 알고리즘은 반복적인 요소를 가진다. 귀납법은 반복적인 알고리즘이 옳은 답을

계산함을 보이기 위해 각 단계가 정답으로 가는 길 위에 있음을 보인다.

 

반복문 불변식(loop in variant)은 반복문이 실행될 때마다 중간 결과가 원하는 답으로

가는 길에 잘 있는지 명시하는 조건으로, 항상 이 식이 변하지 않고 성립해야 한다.

 

다음 절차를 통해 반복문 불변식을 작성할 수 있다.

 

 1. 반복문 진입시 불변식 성립을 보인다.

 2. 반복문 시작시 불변식이 성립하면 끝날 때도 항상 성립함을 보인다.

 3. 반복문 종료시에 불변식이 성립하면 항상 정답이 구해짐을 보인다.

 

이진 탐색을 예로 들어보자.

 

// A[-1] : -infinite , A[n] : +infinite
int binarySearch(const vector<int>& A, int x){
    int n = A.size();
    int lo = -1, hi = n;
    
    // 불변식 1: lo < hi
    // 불변식 2: A[lo] < x <= A[hi]
    // 여기에서 불변식은 성립.
    while(lo + 1 < hi){
        int mid = (lo + hi) / 2;
        if(A[mid] < x) lo = mid;
        else hi = mid;
        // 여기에서도 불변식은 성립.
    }
    return hi;
}

 

 

반복문 진입 초기에 lo = -1, hi = n으로 초기화된 상태이고, n이 0보다 커야 반복문에

진입하므로 불변식 1 은 성립한다. A[-1] = -infinite, A[n] = +infinite 로 가정하므로 

불변식 2 역시 성립한다.

 

반복문이 돌아갈 때,  lo 와 hi 가 2 이상 차이나야 반복문에 진입 (1 차이나면 lo + 1 = hi)

하므로 mid 는 항상 두 값 사이다. 따라서 lo 또는 hi 에 mid 를 대입해도 불변식 1 은 항상

성립한다.

 

A[mid] < x 일 때, 반복문 진입 시 x < A[hi] 이므로 A[mid] < x < A[hi]이다. 따라서

lo 에 mid 를 대입해도 불변식 2 는 성립한다.

 

x < A[mid] 일 때, 반복문 진입 시 A[lo] < x 이므로 A[lo] < x < A[mid]이다. 따라서

hi 에 mid 를 대입해도 불변식 2 는 성립한다.

 

불변식의 성립으로 알 수 있는 사실은,

 

 1. lo + 1 = hi : 반복문이 종료했으므로 lo + 1 >= hi 인데, 불변식에 의해 lo < hi 이므로

lo + 1 = hi 일 수밖에 없다.

 2. A[lo] < x <= A[hi]: 불변식이 성립하므로 이것은 당연히 성립한다. 

 

위의 두가지 사실을 종합하면 x = hi 라는 결론에 도달할 수 있다.

귀류법

원하는 바와 반대되는 상황을 가정하고 논리를 전개해 결론이 잘못됨을 찾아내는 증명 기법.

비둘기집의 원리

10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기집이

반드시 하나는 있다.