[알고리즘 문제해결 전략]5장. 알고리즘의 정당성 증명

Preview

---

 알고리즘의 정확한 증명을 위해서 수학적인 기법을 동원하여 증명한다.

 

1. 귀납법

2. 귀류법

3. 그외 다른 기술들

1. 귀납법

---

반복적인 구조를 갖는 명제들을 증명하는데 유용하게 사용된다.

단계를 나눠 보자

1단계    증명하고 싶은 사실을 여러 단계로 나누자.

2단계    첫단계의 내용이 성립함을 보이자.

3단계    한 단계에서 증명하고 싶은 내용이 성립한다는 가정하에 그 다음 단계도 성립함을 보이자.

반복문을 통해 귀납법의 정당성을 고려해 보자

1단계	반복문 진입시에 불변식이 성립함을 보인다.
2단계	반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면, 반복문 내용이 시작할때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.
3단계	반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 말한다.

EX>

int binsearch(const vector<int>& A, int X){
    int n = A.size();
    int lo = -1, hi = n;
    while( lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if(A[mid] < x) {
            lo = mid;
        }else{
            hi = mid;
        }
    }
    return hi;
}

[코드 1] 반복문 귀납법

[코드 1]은 반복문을 통해 귀납법 증명의 예시를 들기 위해 가져온 이진 탐색함수이다. 

 

초기조건	while문이 시작할 때 lo와 hi는 초기값 -1과 n으로 초기화된 상태이다. 만약 n=0이라면 while문은 아예 건너뛰에 되므로 불변식 1은 항상 성립한다. 우리는 A[-1] = -∞, A[n] =  ∞으로 가정하기 때문에 불변식 2 또한 성립한다.
유지조건	불변식 1: while문 내부로 들어왔다는 것은 hi와 lo의 차이가 2이상이라는 의미이다. 즉, mid는 항상 두 값사이에 위치하게 된다.  불변식 2:  - A[mid] <x인 경우 : 반복문을 시작할 때 x≤A[hi]인 점은 이미 알고 있었다. 따라서 A[mid]< x ≤ A[hi]이므로, lo에 mid를 대입해도 불변식이 성립한다. - x ≤ A[mid]인 경우 : 반복문을 시작할 때 알고 있었던 A[lo] < x와 합쳐 보면 A[lo]< x ≤ A[mid]를 얻을 수 있다. 따라서 hi에 mid를 대입해도 불변식은 성립한다.

2. 귀류법

---

결론이 잘못되었음을 찾아내는 증명 기법, 어떤 선택이 항상 최선임을 증명해내고자 할때 많이 선택된다.

3. 그외 다른 기술들

---

1.비둘기집 원리

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

2. 순환 소수 찾기

void printDecimal(int a, int b){
    int iter = 0;
    while( a > 0){
        if(iter++ == 1) cout << '.';
        cout << a/b;
        a = (a % b) * 10;
    }
}

우리가 원하는 어떤 답이 존재함을 보이기 위해 사용된다. 답을 실제 예로 들거나 답을 만드는 방법을 실제로 제시함. 

4. 안정적 결혼 문제

 n명의 여성과 남성이 있을때 각각의 여성과 남성은 자신이 원하는 우선순위를 정하고 짝을 지을때 서로 만족하는 결과를 얻을 수 있는 방법은?

1. 처음에 여성들이 모두 자신이 가장 선호하는 남성의 앞에서 프로포즈를 한다. 남성이 그 중 가장 원하는 여성을 고르면 나머지는 제자리로 돌아간다.

2. 제자리로 간 여성들은 (상대방이 짝이 있건 없건) 다음으로 마음에 드는 여성에게 간다. 남성은 현재 자기 짝보다 더 맘에 드는 여성이 있으면 원래의 파트너를 제자리로 보내고 새 여성에게 돌아간다.

3. 제자리에 있는 여성이 없을 때까지 2번을 반복한다.

4. 출처

---

[코드 1]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.131(코드 5.1)

[코드 2]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.139