[Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 4

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

 

2019/07/02 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 1

2019/07/09 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2

2019/07/09 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 3

---

해당 포스트는 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략"을 읽고 간단하게 정리한 포스트입니다.

 

 

 

정당성 증명

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

수학적 귀납법

1. 단계 나누기
2. 첫 단계 증명하기
3. 귀납 증명하기

반복문 불변식

1. 반복문 진입시, 불변식이 성립함을 보인다.
2. 반복문 내용이 불변식을 깨트리지 않음을 보인다. 즉, 반복문의 시작에 반복식이 성립했다면 반복문의 끝에서더 불변식이 성립함을 보인다.
3. 반복문 종료시, 불변식이 성립한다면 정답을 구했음을 보인다.

1과 2를 증명했다면, 귀납법을 이용해 반복문이 종료할 때 까지 불변식이 성립함을 보일 수 있습니다.

 

이진탐색 코드를 보면서 이해를 해 봅시다.

// 전제 : A는 정렬되어 있다.
// 결과 : A[i-1] < x <= a[i]인 i를 반환한다.
// A[-1] = 음의 무한대, a[n] = 양의 무한대로 가정한다.
int binarySearch(int[] A, int x) {
    int n = A.size();
    int start = -1;
    int end = n;
    
    // 반복문 불변식 1 : start < end
    // 반복문 불변식 2 : A[start] < x <= A[end]
    while(start + 1 < end) {
        int mid = (start + end) / 2;
        
        if(A[mid] < x) start = mid;
        else end = mid;
    }
    
    return end;
}

코드를 보니 뭔가 느껴지시나요?

두 불변식이 while문이 다 끝날때 까지 성립한다고 가정하다면 다음 두가지 사실을 알 수 있습니다.

• start + 1 = end
  • while문을 탈출했으니 start+1 >= end임을 알 수 있습니다. 그러나 불변식에 의하면 start < end이니, start+1 = end일 수 밖에 없습니다.
• A[start] < x <= A[end]
  • 불변식이 성립한다고 가정하였으니, 당연히 성립합니다.

A[i-1] < x <= A[i]인 i이므로, 원하는 결과값 i는 end라는 것을 알 수 있습니다. 따라서, 불변식이 while문 중료시에 항상 성립함을 증명한다면, 해당 알고리즘의 정당성은 증명됩니다.

 

초기 조건

while문에 진입할 때, start = -1, end = n으로 초기화되었습니다. 만약 n=0이라면 while문을 건너뛰기 때문에, 불변식 1은 항상 성립합니다. 또한, A[-1] = 음의 무한대,  A[n] = 양의 무한대로 가정했으므로 불변식 2도 성립합니다.

 

유지 조건

while문 내부가 불변식을 깨트리지 않음을 보이면 됩니다.

• 불변식 1
  • while문 내부로 들어왔다는 말은, start와 end의 차이가 2 이상이라는 말이므로, mid는 항상 두 값 사이에 위치하게 됩니다. 따라서 mid를 start에 대입하건 end에 대입하건 불변식 1은 항상 만족합니다.
• 불변식 2
  • A[mid] < x : 반복문을 시작할 때 x <= A[end]입니다. 따라서 A[mid] < x <= A[end]이므로, start에 mid를 대입해도 불변식은 성립합니다.
  • x <= A[mid] : 반복문을 시작할 때 A[start] < x입니다. 따라서 A[start] < x <= A[mid]이므로, end에 mid를 대입해도 불변식은 성립합니다.

 

 

 

귀류법

어떤 명제가 참임을 증명하려 할 때 그 명제의 결론을 부정함으로써 가정(假定) 또는 공리(公理) 등이 모순됨을 보여 간접적으로 그 결론이 성립한다는 것을 증명하는 방법이다.

네이버 지식백과에 따르면 귀류법은 반증을 통해 명제를 증명하는 방법이라고 합니다. 즉, 원하는 바와 반대되는 상황을 가정하고 논리를 전개하여, 결론이 잘못됬음을 증명하는 것입니다.

귀류법은 어떤 선택이 최선임을 증명하기 위해 많이 사용한다고 합니다.

 

 

책장 쌓기

상자형태의 책장을 여러개 쌓아올리려고 합니다. 각 책장이 버틸 수 있는 최대 무게 Mi와 현재 무게 Wi, i번 책장 위에 쌓인 모든 책장의 집합을 나타내는 abobe(i)가 주어진다고 가정합니다.

 

$$\sum_{j\in above(i)}W_{j}\le M_{i}$$

위와 같은 가정 하에, 위 식은 만족되어야 합니다. 즉, 특정 책장 위에 올라간 다른 책장들의 무게의 합이 특정 책장이 버틸 수 있는 최대 무게를 초과하면 안된다는 말입니다.

 

이 문제를 해결하기위한 첫번째 단계는 책장을 쌓는 순서를 결정하는 것입니다. 즉, Mi + Wi가 큰 순서대로 먼저 쌓아야 합니다. (이를 명제 P라고 하겠습니다.)

이제, 이 명제 P를 귀류법을 이용해 증명해보도록 하겠습니다. 위에서 Mi + Wi가 큰 순서대로 쌓아야 한다고 했으니, 역으로서 Mi + Wi가 더 큰 책장 A가 더 작은 B 책장 위에 올라갔따고 가정해봅시다. (이를 명제 Q라고 하겠습니다.) 이 때, A와 B의 위치를 항상 바꿀 수 있음을 증명합니다. 그러면 Mi+Wi가 큰 것이 밑에 가도록 쌓아도 최선의 답을 얻을 수 있다는 것을 증명할 수 있습니다. (명제 P가 조건을 만족한다면 명제 Q가 유일한 최선의 해가 아니게 되기 때문입니다.) 여기서 관건은, A가 B를 포함한 위쪽의 책장 무게를 견딜 수 있느냐 입니다. 따라서, 다음과 같은 식을 세웁니다.

 

$$M_{A}+W_{A}\lt M_{B}+W_{B}$$

$$M_{A}\lt M_{B}+W_{B}-W_{A}$$

A위의 책장들의 무게의 합을 X라고 합시다. 최선의 답에서 A가 B위로 올라가도록 바뀌엇으니 $M_{B}\le W_{A}+X$가 됩니다. 위 식들을 합치면 다음과 같습니다.

$$M_{A}\lt M_{B}+W_{B}-W_{A}\le (W_{A}+X)+W_{B}-W_{A}$$

$$M_{A}\lt M_{B}+X$$

이 말은 A가 B를 포함한 책장들을 지탱할 수 있다는 뜻입니다. 따라서, A가 위에, B가 아래에 위치하도록 하는 방법은 최선의 해가 아님을 알 수 있습니다. (만약 A가 B를 포함한 책장들을 지탱할 수 없다면, 명제 Q가 최선의 해라는 뜻이겠죠.)

결국, Mi + Wi가 큰 순서대로 먼저 쌓았을 때, 가장 높은 탑을 얻지 못하는 경우는 존재하지 않는다는 것을 알 수 있습니다.

 

 

다른 원리들

비둘기집의 원리

동전 뒤집기

순환소수 찾기

 

구성적 증명

안정적 결혼 문제

 

 

 

참고

구종만.프로그래밍 대회에서 배우는 알고리즘 해결전략. 서울:인사이트, 2012.