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

알고리즘

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

강철곰탱이 2023. 7. 25. 03:13

❗️이 글은 구종만 - 알고리즘 문제해결 전략 책을 참고하여 작성되었습니다.

해결해야하는 간단한 알고리즘은 직관적으로 문제를 해결할 수 있지만, 문제가 복잡해지면 알고리즘이 이 문제를 제대로 해결하는지 확인하기 어렵다.

알고리즘의 정확한 증명을 하기 위해 각종 수학적인 기법이 동원되어야 한다.

알고리즘의 증명은 알고리즘의 유도 과정에 대한 통찰을 담고 있다. 그렇기 때문에 증명을 제대로 이해해야 알고리즘을 제대로 공부했다고 할 수 있다.

📝 목차

1. 수학적 귀납법과 반복문 불변식
2. 귀류법
3. 다른 기술들

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

📍 수학적 귀납법

예를 들어 100개의 도미노가 순서대로 놓여있다고 해보자. 그리고 우리가 다음 두 가지 사실은 안다고 가정해보자.

첫번째 도미노는 직접 손으로 밀어서 쓰러뜨린다.
한 도미노가 쓰러지면 다음 도미노 역시 쓰러진다.

=> 최종적으로 마지막 도미노가 쓰러진다는 것을 직관적으로 알 수 있다.

수학적 귀납법

: 모든 자연수가 주어진 어떤 성질을 만족시킨다는 명제를 증명하는 방법

수학적 귀납법은 3가지 단계로 나눠진다.

단계나누기: 증명하고 싶은 사실 여러 사실로 나누기
첫 단계 증명: 그 중 첫 단계에서 증명하고 싶은 내용이 성립함을 보여라.
귀납 증명: 한 단계에서 증명이 성립하면, 다음 단계에서도 성립함을 보여라.

1️⃣ 위의 도미노 예제에 적용시켜 보면,

100개의 도미노를 하나씩 나눠 100단계를 만들자.
첫번째 도미노가 넘어짐을 증명하자.
한 도미노가 쓰러지면, 다음 도미노는 반드시 쓰러짐을 증명하자.

2️⃣ 다른 예로 사다리 타기에도 적용시켜보자.

텅 빈 N개의 세로줄에서부터 시작해서 가로 줄을 하나씩 그어가는 단계를 한 단계로 정하자.
텅 빈 N개의 세로줄에서는 항상 맨 위 선택지와 맨 아래 선택지가 1:1 대응이다.
가로줄을 그어 두 개의 세로줄을 연결하면 두 세로 줄의 결과는 서로 바뀐다.
결과가 바뀌어도 1:1 대응은 유지된다.

📍반복문 불변식

귀납법을 이용해 알고리즘의 정당성을 증명할 때 주로 사용된다.

반복문 불변식

: 반복문의 내용을 실행할 때마다 중간 결과가 원하는 결과로 가는 길이 맞는지 명시하는 조건

✏️ 반복문의 정당성 증명

반복문 진입시에 불변식이 성립함을 보인다.
반복문 내용이 시작할 때 불변식이 성립했다면, 내용이 끝날때도 항상 성립함을 보인다.
반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

=> 1번과 2번항목을 증명했다면 수학적 귀납법을 통해 반복문이 종료할 때까지 항상 이 불변식이 성립함을 보일 수 있다.

// (*) 불변식은 여기서 성립해야 한다.
while (조건식) {
    // 반복 내용 시작
    ...
    // 반복 내용 끝
    // (**) 불변식은 여기서도 성립해야 한다.
}

📍 이진탐색과 반복문 불변식

// 필수 조건: 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;
}

위의 코드는 이진 탐색 구현에 대한 로직을 가진다.

이진 탐색 내부의 while문에서 두개의 불변식을 유지한다.

lo<hi : while문이 종료하면 lo+1>=hi 인데, 불변식이 의하면 lo<hi이니 lo+1=hi일 수 밖에 없다.
A[lo]<x<A[hi] : 불변식이 성립한다 가정했으니, 당연히 성립한다.

반복문 불변식을 증명하는 과정은 귀납법과 다를게 없다.

1️⃣ 초기조건

: while문이 시작할 때 lo와 hi는 초기값 -1과 n으로 초기화된 상태

n=0이라면 while문을 건너뛰어 불변식 1은 성립
A[-1]=-∞, A[n]=∞이라고 불변식 2도 성립

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]인 경우: 반복문을 시작할 때 A[lo]<x와 합쳐보면 A[lo]<x<=A[mid] 얻는다.
  => hi에 mid 대입해도 성립한다.

📍 삽입 정렬과 반복문 불변식

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--;
        }
    }
}

위의 코드는 삽입 정렬 알고리즘을 구현한 것이다.

1️⃣ 초기조건

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

2️⃣ 불변식 유지

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...j-1]은 정렬되어 있어 while문 진입시 (c)는 항상 참이다.
(c) 유지조건: A[j]와 이전 원소를 교체해도 상대적 순서는 변하지 않아 (c)는 항상 유지된다.

=> 위의 증명은 while문이 항상 A[0...i]를 정렬된 상태로 남겨둔다는 것을 불변식 (a)의 유지조건이 된다.

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

불변식을 주석으로만 달아 놓을 것이 아니라 단정문으로 강제해버리면,

해당 불변식이 깨졌을 때 프로그램이 강제 종료되기 때문에 불변식의 유지에 문제가 있다는 것을 알 수 있다.

단정문도 어느 정도 속도에 지장을 주기 때문에 많이 실행되는 반복문 안에 단정문 배치하는 것은 삼가하는게 좋다.

2. 귀류법

귀류법

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

만약 기차 사이트 오류로 규정보다 많은 인원이 표를 예매한 경우, 열차에서 쫓겨나는 승객의 수를 최소화하기 위해
A(가장 멀리 가는 사람), B(도중에 하차하는 사람) A와 B 중 누구를 쫓아낼 것인가?

A대신 B를 쫓아냈을 때, 쫓겨나는 승객의 수가 더 적을 수가 있는가?

=> 이런 일은 불가능하다.

B는 쫓아냈을 때 기차에 탈 수 있는 사람이 변하지 않을 수 있지만 쫓아낸다고 해서 얻는 이득은 없다.

A는 쭉 한 자리에 앉아 가기때문에 다른 사람이 탈 수 있는 기회가 더 적다.

📍 예시: 책장 쌓기

수정 필요

📍 귀류법을 이용한 증명들

알고리즘의 결과가 최선임을 보이기 위해 각 단계에서 최선의 선택을 함을 귀류법으로 증명

각 단계에서 최선의 선택을 하면 다음 단계에서도 최선의 선택을 할 수 있음을 귀납법으로 증명

3. 다른 기술들

📍 비둘기집의 원리

만약 머리숱이 적을수록 세금을 적게 부과하는 탈모자 위로 법안이 있을때, 서울의 모든 사람들이 머리털 개수를 셀 것이다.
이들 중 머리털 개수가 정확히 같은 두 사람이 존재할까?

비둘기집의 원리를 생각해보자.

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

너무나 당연한 말이다. 똑같은 원리를 머리털 문제에도 적용시켜보자.

서울의 인구가 약 천만명
사람은 평균적으로 약 10만 가닥의 머리털을 가진다.

=> 머리털 개수가 정확히 같은 사람은 반드시 존재한다.

천만마리의 비둘기가 백만개의 비둘기 집에 들어갔다면,

=> 2마리 이상이 들어간 비둘기 집이 반드시 하나는 있다.

📍 동전 뒤집기

✔️ 문제

100개의 동전이 바닥에 깔려있는데 이 중 F개는 앞면, 100-F개는 뒷면이 위로 놓여있다.

동전들이 모두 앞면을 위로하게 뒤집고 싶을 때 뒤집는 횟수의 상한은 얼마인가?

✔️ 조건

반드시 X개의 동전 한꺼번에 뒤집어야 한다.
같은 동전 두 번 이상 뒤집어도 된다.

✔️ 답

정답은 100이다.

동전을 한번 뒤집을 때마다 보이는 앞면의 개수를 적는다고 하자.
만약 동전을 101번 뒤집었다면, F까지 합쳐 102개의 숫자를 적게된다.
앞면의 개수는 0부터 100까지 101가지의 값만 가질 수 있다.

=> 비둘기집의 원리에 따라 중간에 반드시 중복이 발생할 수밖에 없다.

✚ 보너스 문제

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

초기 상태: 앞면이 보이는 동전 57개(홀수)
불변식 유지: 한번에 2개의 동전만 뒤집을 수 있어 앞면의 수가 항상 홀수이다.
앞면의 수가 짝수인 100이 될 수는 없다.

=> 귀납법 사용

📍 순환 소수 찾기

분수 a/b가 주어질 때, 실수 연산을 사용하지 않고 이 분수를 소수 형태로 출력시켜보자.

// 분수 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;
    }
}

위와 같은 함수에 1/11을 넣으면 어떻게 될까? 0.09090909... 로 무한히 반복될 것이다.

무한 소수를 인식하여 별도로 처리해줘야 하는데 어떻게 인식할 수 있을까?

비둘기집의 원리

a=(a%b)*10 에서 a%b의 결과는 언제나 [0, b-1]범위의 값을 가진다.
while문이 b+1번 반복될 때까지 함수가 종료하지 않았다고 하면,
a%b의 결과는 b가지의 결과만 가질 수 있어 결과가 중복되는 경우가 반드시 있다.

=> 같은 결과가 첫 번째로 등장했을 때부터 두 번째 등장할 때까지 무한히 순환되는 순환 소수임을 알 수 있다.

📍구성적 증명

구성적 증명

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

예를 들어 하늘을 나는 교통수단을 만들 수 있다는 주장을 증명하고자 할 때,

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

📍 안정적 결혼 문제

문제 상황
n명의 남성과 여성이 단체 미팅에서 만난 경우, 게임을 진행하며 모든 사람은 자신이 원하는 상대방의 우선순위를 정했다고 해보자.
시간이 되어 서로 짝을 만들어줄 때, 우선순위에 따라 원하는 짝을 만들어줄 수는 없을까?

🔎 구성적 증명으로 해결

이 알고리즘은 다음과 같이 진행된다.

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

1️⃣ 종료 증명

각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈한다.
각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 후 더 이상 프로포즈할 남성이 없어 언젠가 반드시 종료한다.

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

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

귀류법을 적용하여,

남녀가 한 사람씩 짝을 찾지 못해 남았다고 하자.
여성은 우선순위가 높은 순서대로 모두에게 프로포즈하기 때문에, 해당 남성에게도 프로포즈한다.
남성은 프로포즈 한 여성 중에 무조건 선택해야하니 짝을 찾지 못하는 사람은 없다.

3️⃣ 짝들의 안정성

귀류법으로 증명

짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정하자.
여성은 지금 자신의 짝 이전에 우선순위가 더 높은 그 남성에게 반드시 프로포즈했어야 한다.
남성은 지금 짝보다 더 우선순위가 높은 여성이 오면 짝을 바꿀 수 있다.

=> 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 짝이 되는 일은 없다.