[02 알고리즘 분석] 5. 알고리즘의 정당성 증명

1. 도입

 

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

 

전 세계 99%의 프로그래머는 알고리즘을 새로 만들기보다 배워서 써먹는 쪽에 지대한 관심을 가지고 있습니다. 그래서 대개 알고리즘의 증명에 관해서는 일찌감치 잊어버리는 게 어떨까 하는 유혹을 받기가 쉽고요. 하지만, 알고리즘의 증명을 이해하지 않고서는 알고리즘을 제대로 공부했다고 할 수 없습니다.

 

알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문입니다. 모든 알고리즘은 사실 치열한 고민과 개선 과정을 거쳐 태어납니다. 이 과정에서 결정적으로 필요한 깨달음이 증명에 담겨 있는 경우가 많습니다. 따라서 의사 코드를 달달 외우기만 해서는 알고리즘에 담겨 있는 깨달음을 제대로 흡수했다고 볼 수 없으며, 증명을 이해하는 편이 알고리즘을 사용하는 입장에서도 더 큰 공부가 됩니다.

 

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

 

100 개의 도미노가 순서대로 놓여 있는 광경을 상상해 봅시다. 그리고 우리가 다음 두 가지 사실을 안다고 가정합시다.

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

그러면 마지막 도미노 또한 당연히 쓰러진다는 것을 직관적으로 알 수 있지요. 수학적 귀납법(mathematical indunction)은 이와 같이 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법입니다. 귀납법 증명은 크게 세 단계로 나누어집니다.

• 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눕니다. 앞의 예에서는 100개의 도미노를 도미노 하나씩으로 나누었죠. 이 과정은 너무 당연해서 잊어버리기 쉽지만 가끔은 중요할 때가 있습니다.
• 첫 단계 증명 : 그중 첫 단계에서 증명하고 싶은 내용이 성립함을 보입니다. 앞의 예에서는 첫 번째 도미노가 넘어짐을 증명하는 것이 이 과정이죠
• 귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보입니다. 앞의 예에서는 한 도미노가 쓰러지면 다음 도미노는 반드시 쓰러짐을 보이는 것이 이 과정이지요.

실제 귀납법을 이용한 증명의 예로 사다리 게임을 생각해 봅시다. 사다리 게임을 하다 보면 맨 위 선택지와 맨 아래 선택지가 언제나 1:1 대응이 되는 것이 신기할 때가 있습니다. 귀납법을 이용하면 이 사실을 쉽게 증명할 수 있습니다.

 

• 단계 나누기 : 텅 빈 N개의 세로줄에서부터 시작해서 원하는 사다리가 될 때까지 하나씩 가로 줄을 그어 간다고 합시다. 이때 가로 줄을 하나 긋는 것을 한 단계라고 하지요.
• 첫 단계 증명 : 텅 빈 N개의 세로줄에서는 항상 맨 위 선택지와 맨 아래 선택지가 1:1 대응이 됩니다.
• 귀납 증명 : 가로줄을 그어서 두 개의 세로줄을 연결했다고 하죠. 이때 두 세로줄의 결과는 서로 뒤바뀝니다. 두 세로줄의 결과가 뒤바뀌어도 1:1 대응은 변하지 않으므로 다음 단계에서도 1:1 속성이 유지되지요.

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

 

반복문 불변식

귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법입니다. 왜냐면 대부분의 알고리즘은 어떠한 형태로든 반복적인 요소를 가지고 있기 때문입니다. 귀납법은 이런 알고리즘들이 옳은 답을 계산함을 보이기 위해서 알고리즘의 각 단계가 정답으로 가는 길 위에 있음을 보이고, 결과적으로는 알고리즘의 답이 옳음을 보입니다.

 

귀납법을 이용해 알고리즘의 정당성을 증명할 때는 반복문 불변식(loop in-variant)이라는 개념이 유용하게 쓰입니다. 반복문 불변식이란 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건입니다. 반복문이 마지막에 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 (그래서 불변식입니다) 성립해야 하는 것이죠.

 

불변식을 이용하면 반복문의 정당성을 다음과 같이 증명할 수 있습니다.

 

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

실제 적용 예를 위해 이진 탐색 알고리즘을 보도록 합시다.

// 필수 조건: A는 오름차순으로 정렬되어 있다.
// 결과: A[i - 1] < x <= A[i] 인 i를 반환한다.
// 이때: A[-1] = 음의 무한대, A[n] = 양의 무한대라고 가정한다.
int binsearch(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 이고, 두 번째는 A[lo] < x <= A[hi] 이지요.이 불변식이 while 문이 완전히 종료하고 함수의 마지막 줄에 올 때까지 계속 성립했다고 가정해 봅시다. 그러면 다음 두 가지 사실을 알 수 있지요.

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

우리가 원하는 결과값 i는 A[i-1] < x <= A[i] 인 i이므로 이때 우리가 원하는 답은 hi라는 사실을 쉽게 알 수 있지요. 따라서 불변식이 while문 종료시에 항상 성립한다는 것을 보인다면 이 알고리즘의 정당성은 증명한 셈입니다.

 

불변식을 이용해 반복문의 정당성을 증명하는 과정은 귀납법과 다를 것이 없습니다. 전체 작업을 각 단계로 나누는 과정이 이미 반복문으로 나타나 있으니 더 간단하지요. 반복문이 처음 시작될 때 해당 불변식이 만족함을 보이고, 반복문 내용이 한 번 지나가도 이 조건이 다시 유지됨을 보여 주면 됩니다. 엄밀하게 다음과 같이 증명할 수도 있습니다.

 

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

이런 과정을 거쳐 while 문이 종료될 때 우리가 원하는 값이 A[hi]에 저장되어 있음을 알 수 있습니다. 반복문 불변식은 이와 같이 알고리즘의 정당성을 증명하기 위한 좋은 도구입니다. 까다로운 코드를 짤 때 해당 코드가 가져야 할 불변식을 파악하고 작성하면 좀 더 오류가 적은 코드를 작성할 수 있습니다.

 

3. 귀류법

 

지금 막 출발한 완행 열차의 차장이 철도청 웹사이트의 오류 때문에 규정 인원보다 많은 승객이 표를 예매했다는 것을 깨달았다고 합시다. 다행히 처음에는 자리가 남아 있었지만 앞으로 지나칠 역에서 승객들이 더 탑승하면 열차가 미어터질 것이 뻔한 상황이지요. 차장은 안전 규정을 어기느니 원성을 듣더라도 일부 승객에게 내려서 다음 열차를 기다리라고 말하고 싶습니다. 각 승객이 어느 역에서 승차해 어느 역에서 하차할지를 모두 알고 있을 때, 열차에서 쫓겨나는 불쌍한 승객의 수를 최소화하기 위해서는 누구를 쫓아내는 것이 좋을까요?

 

현명한 차장의 선택은 바로 가장 멀리 가는 사람들입니다. 역에 정차할 때마다 승객들 중 멀리 가는 순서대로 안전 규정을 초과하는 인원수만큼을 내쫓는 것이죠. 왜 이 방법이 최선일까요?

 

이 질문에 답하기 위한 좋은 방법은 가장 멀리 가는 사람을 내쫓는 대신 다른 사람을 내쫓았다고 가정하고 논리를 전개해 보는 것입니다. 차장이 차내를 둘러보니 다음 역까지 가는 비실비실하게 생긴 청년과 종착역까지 가는 우락부락한 할아버지가 있었습니다. 할아버지에게 겁을 먹은 차장이 청년을 대신 쫓아냈는데, 다행히 결과적으로 할아버지를 쫓아냈을 때보다 쫓겨나는 사람의 수가 더 적었다고 합니다. 이런 일이 있을 수 있을까요?

 

물론 이런 일은 불가능합니다. 청년을 태웠을 경우와 할아버지를 태웠을 경우를 비교해 봅시다. 청년을 태웠다면 청년이 내린 뒤 그 자리에 사람을 더 태울 수 있을 겁니다. 반면 할아버지를 태웠다면 그 자리는 쭉 할아버지가 앉아 있었겠지요. 경우에 따라서는 청년을 쫓아냈을 때에도 기차에 탈 수 있는 사람의 수가 변하지 않을 수는 있겠지만, 청년을 쫓아내는 것이 이득인 상황은 없습니다.

 

이와 같이 우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법을 귀류법이라고 합니다. 귀류법은 대게 어떤 선택이 항상 최선임을 증명하고자 할 때 많이 이용됩니다. 우리가 선택한 답보다 좋은 답이 있다고 가정한 후에, 사실은 그런일이 있을 수 없음을 보이면 우리가 최선의 답을 선택했음을 보일 수 있으니까요.

 

책장 쌓기

상자 형태로 된 책장을 여러 개 쌓아올리려고 합니다. 무거운 것부터 가벼운 것, 책만 꽂아도 부서질 것 같은 비실비실한 것부터 코끼리가 올라가도 될 것 같은 튼튼한 것까지 다양한 책장들이 있습니다. 각 책장마다 버틸 수 있는 최대 무게 M(i)와 자신의 무게 W(i)가 주어진다고 합시다. 이때 책장을 가장 높이 쌓는다면 몇 개나 쌓을 수 있을까요? 단 above(i)가 i번 책장 위에 쌓인 모든 책장의 집합이라고 할 때, 다음이 성립해야 합니다.

 

j ∈ above(i) ∑ W(j) <= M(i)

 

다시 말해 책장 위에 올라간 다른 책장들의 무게의 합이 견딜 수 있는 최대 무게를 초과하면 안 된다는 말이지요.

 

이 문제를 풀기 위한 첫 번째 관문은 책장을 쌓는 순서를 결정하는 것입니다. 가장 높이 책장을 쌓았을 때, 책장들이 항상 어떤 순서를 가진다는 것을 보일 수 있다고 합시다. 예를 들어 항상 가장 무거운 책장을 아래쪽에 쌓는 것이 좋다는 사실을 알고 있다면, 처음에 주어진 책장들을 가벼운 것부터 무거운 것까지 정렬한 뒤 이제는 순서에 신경 쓰지 않고 어느 책장을 고를 것인가에만 집중할 수 있기 때문입니다. 다행히도 이 문제에서는 그런 순서가 존재합니다.

 

W(i)로 정렬해 가장 무거운 책장일수록 아래에 놓아야 할까요? 아니면 M(i)로 정렬해 가장 튼튼한 책장을 아래에 놓아야 할까요? 정답은 견딜 수 있는 최대 무게와 자신의 무게의 합 다시 말해 M(i) + W(i) 가 큰 것부터 아래에 놓아야 한다는 것입니다.

 

이것을 증명하기 위해 귀류법을 써 봅시다. 귀류법을 쓰기 위해서는 우리가 증명하려는 사실의 반대를 가정해야 하죠. 어떤 입력의 최적해를 구했는데 M(i) + W(i) 가 더 큰 책장 A가 더 작은 책장 B 위에 올라간 형태라고 가정해 봅시다. 합이 큰 것부터 아래에 놓아야 하는데 A가 B 위에 올라가 있으니 이것은 우리가 원하는 바와 반대지요. 이때 A와 B의 위치를 항상 바꿀 수 있음을 증명해봅시다. 그러면 M(i) + W(i) 가 큰 것이 밑에 가도록 책장을 쌓아도 최선의 답을 얻을 수 있다는 증거가 되지요. B는 윗칸으로 올라가니 견뎌야 할 무게가 더 줄어들고, 반드시 위에 올릴 수 있습니다. 문제는 기존에 위에 있던 상자들에 더해 B의 무게까지를 A가 견딜 수 있느냐는 것입니다. 그러니 부등식 M(A) + W(A) > M(B) + W(B) 에서 M(A) 만을 좌변에 남겨봅시다.

 

M(A) > M(B) + W(B) - W(A)

 

A 위에 올라가 있는 상자들의 무게의 합을 X 라고 합시다. 가장 좋은 답에서 A가 B 위에 올라갔으니 M(B) >= W(A) + X 임을 알 수 있지요. 이것과 위 식을 합쳐보면 다음과 같습니다.

 

M(A) > M(B) + W(B) - W(A) >= (W(A) + X) + W(B) - W(A)

 

맨 오른쪽의 W(A) 들이 더하고 빠지면 다음 식만 남습니다.

 

M(A) > X + W(B)

 

이 말은 A도 B와 나머지 모든 상자들을 지탱할 수 있다는 말이지요. 따라서 우리가 원하는 순서대로 쌓았을 때 가장 높은 탑을 얻지 못하는 경우는 존재하지 않는다는 것을 알 수 있습니다.

최적해는 책장 A가 책장 B 위에 올라가 있는 상황이었는데, 도출한 식을 통해 책장 A와 책장 B의 위치를 바꾸는 것도 성립한다는 것을 보임. 그러면 책장 B가 책장 A 위에 올라가 있는 상황도 최적해가 된다는 말인데 이것은 초기 전제와 모순됨. 즉, 어떤 입력의 최적해를 구했을 때 M(i) + W(i) 가 더 큰 책장 A가 더 작은 책장 B 위에 올라간 형태라는 전제는 거짓이 되어 M(i) + W(i) 가 더 큰 책장 A 가 더 작은 책장 B 밑에 내려간 형태가 최적해라는 가정이 참이 된다.

 

4. 다른 기술들

 

비둘기집의 원리

머리숱이 적을수록 세금을 적게 부과하는 탈모자 위로 법안이 통과되었습니다. 서울의 모든 사람들이 전부 날밤을 새 가며 머리털 개수를 세어 세금 면제 서류를 제출했습니다. 이들 중 머리털 개수가 정확히 같은 두 사람이 과연 존재할까요?

이처럼 얼핏 보면 대답하기 힘든 질문을 대답하는 데 유용하게 쓰이는 것이 바로 비둘기집의 원리입니다. 비둘기집의 원리를 한마디로 설명하면 다음과 같습니다.

 

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

 

너무 당연하게 느껴지시나요? 똑같은 논리를 아까 머리털 문제에도 적용해 봅시다. 서울의 인구는 천만 명이 약간 넘는다고 합니다. 사람의 머리에는 평균적으로 10만 가닥의 머리털이 있다고 하는데, 넉넉하게 잡아서 머리털이 제일 많은 사람이 100만 가닥 있다고 하겠습니다. 천만 마리의 비둘기가 백만 개의 비둘기집에 들어갔다면, 반드시 같은 비둘기집에 들어간 비둘기가 두 마리 이상 있기 마련이죠. 따라서 머리털 개수가 정확히 같은 두 사람은 반드시 존재합니다. 이와 같이 비둘기집의 원리는 별것 아닌 것 같지만 이곳저곳에서 유용하게 사용됩니다.

 

구성적 증명

구성적 증명은 흔히 우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해서 사용됩니다. 답이 존재한다는 사실을 논증하는 것이 우리가 지금까지 이 장에서 다룬 방식이라면, 구성적 증명은 답의 실제 예를 들거나 답을 만드는 방법을 실제로 제시하는 증명이지요.

예를 들어 하늘을 나는 교통 수단을 만들 수 있다는 주장을 증명하려 한다고 합시다. 비구성적 증명은 양력의 법칙에서부터 시작해 지구의 공기 밀도, 사용할 수 있는 재료들의 강도와 탄성들을 하나하나 열거해 가며 이러한 가정 하에서 교통 수단이 하늘을 날 수 있음을 보이려 할 것입니다. 반대로 구성적 증명이 하는 일은 비행기를 만들어서 보여 주거나, 비행기 만드는 법이 적힌 설명서를 건네 주는 것입니다. '답이 존재하는가'에 대한 대답으로 '이렇게 만들면 된다'라고 하는 것이 구성적 증명이기 때문에, 구성적 증명의 내용은 사실상 알고리즘인 경우가 많습니다.

 

안정적 결혼 문제

n명의 남성과 여성이 단체 미팅에서 만났습니다. 여러 게임을 진행하는 동안 모든 사람은 자신이 원하는 상대방의 우선순위를 맘 속에 정했고, 이제 시간이 되어 남자 1호와 여자 1호가, 남자 2호와 여자 2호가 각각 짝이 되었습니다. 그런데 남자 1호와 여자 2호는 자신들의 짝(여자 1호, 남자2호) 보다, 서로를 더 선호한다는 사실을 알게 되었습니다. 이런 일이 일어나지 않도록 짝을 지어줄 수 있는 방법이 항상 있을까요? 아니면 불가능한 경우가 있을까요?

흔히들 안정적 결혼 문제라고 부르는 이 문제는 구성적 증명으로 해결되는 대표적 문제입니다. 이 문제를 푼 사람들은 답의 존재성을 보이는 대신 답을 만드는 알고리즘을 제시함으로써 답이 존재함을 보였습니다.

 

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

 

1. 처음에는 여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 합니다. 남성이 그중 제일 마음에 드는 여성을 고르면 나머지는 퇴짜를 맞고 제 자리로 돌아갑니다.
2. 퇴짜를 맞은 여성들은 (상대에게 짝이 있는지 없는지는 관계없이) 다음으로 마음에 드는 남성에게 다가가 프로포즈합니다. 남성들은 현재 짝이 없다면 찾아온 여성을 선택하고, 짝이 있는데 더 맘에 드는 여성이 다가왔다면 지금의 파트너에게 퇴짜를 놓고 새 여성에게 넘어갑니다.
3. 더 프로포즈할 여성이 없을 때까지 2번 항목을 반복합니다.

이 알고리즘이 우리가 원하는 답을 구할 수 있음을 보이려면 이 알고리즘이 항상 종료한다는 것, 모든 사람이 짝을 찾는다는 것, 그리고 결과적으로 이뤄지는 짝들이 항상 '안정적' 임을 증명해야만 하죠.

 

• 종료 증명
  • 각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈합니다. 따라서 각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없으므로, 이 과정은 언젠가 반드시 종료합니다.
• 모든 사람들이 짝을 찾는지 증명
  • 프로포즈를 받은 남성은 그중 한 사람을 반드시 선택하고, 더 우선순위가 높은 여성이 프로포즈해야만 짝을 바꾸므로 한 번이라도 프로포즈를 받은 남성은 항상 짝이 있기 마련이죠. 귀류법을 적용하여 남녀 한 사람씩 짝을 찾지 못하고 남았다고 가정합시다. 그런데 여성은 우선순위가 높은 순서대로 모두에게 한 번씩 프로포즈하기 때문에 이 남성에게도 한 번은 프로포즈했겠죠. 이 남성은 프로포즈를 받아들였어야 하고, 따라서 짝을 찾지 못한 사람은 있을 수 없습니다.
• 짝들의 안정성
  • 역시 귀류법으로 증명합니다. 이 과정의 결과로 짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정합시다. 여성은 지금 자신의 짝 이전에 그 남성에게 반드시 프로포즈했어야 합니다. 그런데도 이 남성이 이 여성과 짝지어지지 않았다는 말은 더 맘에 드는 여성에게 프로포즈를 받아서 수락했다는 뜻이죠. 남성은 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없습니다. 따라서 우리가 가정했던 상황은 존재할 수 없지요.