[Algorithm Strategies] 2-5. 알고리즘의 정당성 증명

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.

📚 목차
1. 도입
2. 수학적 귀납법과 반복문 불변식
3. 귀류법
4. 다른 기술들

---

1️⃣ 도입

알고리즘의 정당성 증명을 위해 사용하는 기법들을 다룬다.

---

2️⃣ 수학적 귀납법과 불변식

수학적 귀납법 (mathmetical induction)

반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법

증명과정

1. 단계 나누기

   증명하고 싶은 사실을 여러 단계로 나눔

2. 첫 단계 증명

   첫 단계에서 증명하고 싶은 내용이 성립함을 보임

3. 귀납 증명

   첫 단계 이후의 단게에서도 성립함을 보임

사다리 게임

1. 단게 나누기

   N개의 아무것도 없는 세로줄에서부터 원하는 사다리가 될 때까지 하나씩 가로 줄을 긋는다.
   가로줄을 하나 긋는 것을 한 단계라고 한다.

2. 첫 단계 증명

   N의 아무것도 없는 세로줄인 경우, 맨 위의 선택지와 맨 아래의 선택지는 1:1대응이다.

3. 귀납 증명

   가로줄을 더 추가해도 1:1 대응이다.

   따라서 귀납법에 의해 가로줄만을 사용하는 사다리들은 항상 1:1로 대응이 된다.

반복문 불변식

귀납법을 이용해 알고리즘의 정당성을 증명할 때 쓰이는 개념

반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건

증명과정

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

2. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다.
   반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.

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

이진 탐색과 반복문 불변식

// 코드 5.1 이진 탐색
// 필수 조건: A는 오름차순으로 정렬되어 있다
// 결과: A[i-1] < x ≤ A[i]인 i를 반환한다
// 이때 A[-1] = -∞, A[n] = +∞라고 가정한다
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;
}

위 코드는 두 개의 불변식을 유지한다.

1. lo < hi
2. A[lo] < x <= A[hi]

while문이 완전히 종료하고 함수의 마지막 줄에 올 때까지 계쏙 성립했다고 가정하자.

• lo + 1 = hi : while문이 종료했으니 lo + 1 ≥ hi인데, 불변식에 의해 lo < hi이므로 lo + 1 = hi일 수밖에 없다.
• A[lo] < x ≤ A[hi] : 애초에 불변식이 성립한다고 가정했으므로, 당연히 참이다.

따라서 우리가 원하는 결과값 i는 언제나 hi라는 답을 반환한다. (정당성 증명)

✂️ 전체 작업을 단계로 나누어 보기

초기 조건

while문이 시작할 때, lo와 hi는 각각 -1과 0으로 초기화된 상태이다.
n=0이라면 while문이 실행 안 되므로 불변식 1은 언제나 참이다.
A[-1]과 A[n]을 각각 음/양의 무한대로 가정했으므로 불변식 2도 참이다.

유지 조건

while 내부가 불변식을 깨뜨리는가?

불변식 1

while 문 내부로 들어왔다면 hi와 lo 차이가 2 이상이라는 의미
mid는 언제나 두 값의 사이에 위치하므로 불변식이 유지된다.

불변식 2

A[mid] < x : x≤A[hi]는 반복문 시작할 때 참이으므로, A[mid] < x ≤ A[hi]도 성립한다. 따라서 lo에 mid를 대입해도 불변식은 언제나 성립한다.
x ≤ A[mid] : 위와 반대로 생각해보면 hi에 mid를 대입해도 불변식 2는 언제나 성립한다.

삽입 정렬과 반복문 불변식

삽입 정렬

각 원소를 순서대로 고려하면서 이 원소를 앞에 있는 정렬된 부분 수열에 끼워넣는 작업을 반복하는 알고리즘

// 코드 5.2 (불변식이 추가된) 삽입 정렬 알고리즘
void insertionSort(vector<int>& A) {
    for (int i = 0; i < A.size(); ++i) {
        // 불변식 a: A[0..i-1]는 이미 정렬되어 있다.
        // A[0..i-1]에 A[i]를 끼워넣는다.
        int j = i;
        while (j > 0 && A[j - 1] > A[j]) {
            // 불변식 b: A[j+1..i]의 모든 원소는 A[j]보다 크다.
            // 불변식 c: A[0..i] 구간은 A[j]를 제외하면 정렬되어 있다.
            swap(A[j - 1], A[j]);
            j--;
        }
    }
}

초기 조건

반복문이 시작할 때 i=0이면 해당 구간은 비어 있으니 항상 정렬되어 있다고 가정할 수 있다.

불변식 유지

for문의 내용이 종료할 때, 이 불변식이 깨지지 않고 유지됨을 보이려면 while문 정당성 증명이 필수적이다.
while문 정당성 증명은 불변식 (b)와 (c)를 통해 증명할 수 있다.
j=0이면, 불변식 (b)에 의해 A[j]가 A[0..i] 구간 중 가장 작은 수가 된다. 불변식 (c)와 합쳐 보면 A[0..i] 구간 전체가 정렬되었음을 알 수 있다.
j>0 && A[j-1] ≤ A[j] 라면, 불변식 (b)와 합쳐 A[j-1] ≤ A[j] < A[j+1]가 된다. 불변식 (c)와 합쳐 보면 A[0..i] 구간 전체가 정렬되었음을 알 수 있다.

📍 (b)와 (c)가 항상 성립함을 증명하기

(b) 초기 조건 : while문 진입 시 A[j+1 ⋯ i] 구간은 빈 구간이므로 (b)는 참이다.
(b) 유지 조건 : while문 내용 실행되었다는 말은 A[j-1]>A[j]이므로, 이 둘을 교체하고 j를 1 줄여도 (b)는 여전히 참이다.
(c) 초기 조건 : 불변식 (a)에 의해 A[0 ⋯ i-1]는 정렬되었으므로 while문 진입 시에 (c)는 언제나 참이다.
(c) 유지 조건 : A[j]와 이전 원소를 swap해도 상대적 순서는 변하지 않으므로 (c)는 언제나 참이다.
위 증명은 while문이 언제나 A[0 ⋯ i]를 정렬된 상태로 남겨둔다는 것을 보여준다.

단정문을 이용해 반복문 불변식 강제하기

단정문

조건이 참(true)인지 거짓(false)인지를 확인하는 문장.

단정문은 보통 조건문(if문)과 함께 사용된다.
불변식이 깨졌을 때, 단정문으로 프로그램을 강제 종료하는 코드를 추가하면 좋다.
다만, 속도에 지장을 주므로 반복횟수가 많은 곳에 단정문을 배치하는 것은 삼가하자

---

3️⃣ 귀류법

알고리즘에서 귀류법이란 우리가 선택한 답보다 좋은 답이 있다고 가정한 후에, 그 가정이 거짓임을 보이는 것이다.

❔
source에서 sink까지 운행하는 열차가 조금이라도 더 많은 손님을 태우기 위해, 몇몇 승객을 쫓아내야 한다고 가정하자.
쫓아내는 사람의 수를 최소화하고 싶다면, 가장 멀리 가는 사람들을 쫓아내는 것이 현명하다.
왜 그럴까?

❕
가장 멀리 가는 사람(A)을 내쫓지 않고, 도중에 내리는 사람(B)을 쫓아냈다고 가정해보자.
A대신 B를 쫓아냈을 때, 쫒겨나는 사람의 수가 더 적을 수가 있을까? 그런 일은 불가능하다.
B는 어차피 가만히 냅두었어도 도중에 내렸을 승객이므로, 그 뒤에 변화가 없을 수는 있지만 적어도 다른 승객이 탈 수 있는 가능성은 있었다.
하지만 A는 긴 시간 동안 자리를 차지하고 있으므로 그만큼 더 많은 승객을 태울 수 있을 기회가 적다.

귀류법을 이용한 증명들

알고리즘 결과가 최선(최단 경로, 가장 높은 탑)임을 보이기 위해 각 단계에서 최선의 선택을 함을 귀류법으로 증명하고, 각 단계에서 최선의 선택을 한다면 다음 단계에서도 최선의 선택을 할 수 있음을 귀납법으로 증명할 수 있다.

---

4️⃣ 다른 기술들

• 비둘기집의 원리
• 동전 뒤집기
• 순환 소수 찾기
• 구성적 증명
• 안정적 결혼 문제

비둘기집의 원리

얼핏 보면 대답하기 힘든 질문에 대해 대답하는 데 유용하게 쓰인다.

📍 10마리의 비둘기가 9개의 비둘기 집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기 집이 반드시 하나는 있게 마련이다.

❔
서울 시민 중에 머리털 개수가 정확히 같은 두 사람이 존재할 수 있을까?

❕
서울 인구를 1000만 명으로 가정하고, 평균 머리털 개수가 10만 가닥인데, 가장 많은 사람이 100만 가닥이라 가정하자.
천만 마리의 비둘기가 백만 개의 비둘기 집에 들어갔다면, 반드시 같은 비둘기 집에 들어간 비둘기가 두 마리 이상 있기 마련이다.
따라서 머리털 개수가 정확히 같은 두 사람은 반드시 존재한다.

동전 뒤집기

❔
100개의 동전이 F개는 앞면, 100-F개는 뒷면이 위로 놓여져 있다.
동전들을 모두 앞면으로 뒤집고 싶은데, 한 번 뒤집을 때 반드시 X개의 동전을 한꺼번에 뒤집어야 한다. (같은 동전을 두 번 이상 뒤집어도 상관없다.)
뒤집는 횟수를 최소화하고 싶을 때 답의 상한은 얼마인가?

❕
정답은 100이다.

동전을 한 번 뒤집을 때마다 보이는 앞면의 개수를 적는다 치자.
동전을 101번 뒤집었다면 F까지 합쳐 102개의 숫자를 적게 된다.
앞면의 개수는 0부터 100까지 101가지 값만을가질 수 있다.
비둘기집 원리에 따라 중간에 반드시 중복이 발생할 수밖에 없으므로 최선이 아니다.

❓
100개의 동전 중 앞면이 보이는 동전 57개가 있고, 한 번에 2개의 동전만 뒤집을 수 있다면?

❗️
귀납법으로 해결할 수 있다.
초기 상태에서 F = 57이므로 홀수이다. (불변식 성립)
한 번에 2개의 동전을 뒤집을 때, 앞면의 수는 여전히 홀수다. (불변식 성립)
따라서 앞면의 수 T는 언제나 홀수로 유지되므로 100개(짝수)가 될 수가 없다.

순한 소수 찾기

// 코드 5.3 순환 소수 찾기
// 분수 a/b의 소수 표현을 출력한다.
// a >= 0, b > 0이라고 가정한다
void printDecimal(int a, int b) {
    int iter = 0;
    while (a > 0) {
        // 첫 번째와 두 번째 사이에 소수점을 찍는다.
        if (iter++ == 1) cout << '.';
        cout << a / b;
        a = (a % b) * 10;
    }
}

❔
분수 a/b가 주어질 때 실수 연산을 쓰지 않고, 분수를 소수 형태로 출력하려 한다고 하자.
무한 소수인 경우를 걸러내려면 어떻게 해야할까?

❕
비둘기집의 원리를 사용하자.
a%b의 결과는 언제나 [0, b-1]의 범위의 값을 가지므로, while문이 b+1번 반복될 때까지 함수가 종료하지 않았다고 가정하면, a%b 결과는 b가지 결과만 가질 수 있으므로 결과가 중복되는 경우가 반드시 존재한다.
이는 같은 결과가 두 번째 등장할 때까지가 무한히 순환되는 순환 소수임을 알 수 있다.

구성적 증명

구성적 증명

답의 실제 에를 들거나 답을 만드는 방법을 실제로 제시하는 증명

우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해서 사용된다.
'답이 존재하는가'에 대란 대답으로 '이렇게 만들면 된다'라고 하는 것이다.

하늘을 나는 교통 수단을 만들 수 있다는 주장을 증명하려고 하면
비구성적 증명 : 양력의 법칙에서부터 지구의 공기 밀도, 사용할 수 있는 재료들의 강도와 탄성을 열거해 가며 이러한 가정 하에서 교통 수단이 하늘을 날 수 있음을 보여려 할 것이다.
구성적 증명 : 비행기를 만들어서 보여 주거나. 비행기 만드는 법이 적힌 설명서를 건네 주는 것이다.

안정적 결혼 문제

❔
n명의 남성과 여성이 단체 미팅에서 만났다.
남자 1호, 여자 1호와 남자 2호, 여자 2호가 각각 짝이 되었다.
그런데, 남자 1호와 여자 2호는 자신들의 짝(여자 1호, 남자 2호)보다, 서로를 더 마음에 들어한다.
이런 일이 일어나지 않도록 짝을 지어줄 수 있는 방법이 항상 존재할까? 불가능할까?

❕
1. 처음에는 여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 한다. 남성이 그 중 제일 마음에 드는 여성을 고르면 나머지는 퇴짜를 맞고 제 자리로 들어간다.
2. 퇴짜를 맞은 여성들은 다음으로 마음에 드는 남성에게 다가가 프로포즈한다. 남성들은 현재 자기 짝보다 더 맘에 드는 여성이 다가오면, 지금의 파트너에게 퇴짜를 놓고 새 여성에게 넘어간다.
3. 더 프로포즈할 여성이 없을 때까지 2번 항목을 반복한다.

종료 증명

여성은 퇴짜를 맞을 때마다 우선 순위가 낮은 남성에게 찾아간다.
각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없다.
따라서 이 과정은 언젠가 반드시 종료된다.

모든 사람들이 짝을 찾는지 증명

프로포즈를 받은 남성은 반드시 한 사람을 선택한다.
우선 순위가 높은 여성이 프로포즈해야 짝을 바꾸므로, 한 번이라도 프로포즈 받은 남성은 항상 짝이 있다.

짝들의 안정성

짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 선호하는 경우
여성은 반드시 현재 짝 이전에 그 남성에게 프로포즈 했어야 한다.
그러나 매칭이 안 됐다면 해당 남성에게 우선순위가 밀렸다는 의미가 된다.
남성은 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없다.