PART I — 증명
컴퓨터 프로그램은 결국 무엇일까요? 추상적으로 보면 프로그램은 하나의 거대한 상태 기계입니다. 어떤 시작 상태에서 출발해, 한 걸음씩 정해진 규칙대로 다음 상태로 이동하는 시스템이지요. 이 챕터에서는 상태 기계라는 모델을 정식으로 정의하고, 5장에서 배운 귀납을 다시 변주해서 "프로그램이 정말로 옳게 작동하는가"를 증명하는 도구를 만듭니다. 마지막에는 그 도구로 누구나 한 번쯤 들어봤을 안정 결혼 알고리즘까지 분석합니다.
일상적인 비유부터 시작해 봅시다. 신호등은 빨강, 노랑, 초록 세 가지 "상태"를 갖고, 일정한 규칙에 따라 한 색에서 다음 색으로 바뀝니다. 자판기는 동전을 넣은 만큼의 "잔고 상태"를 기억하고, 버튼을 누르거나 동전을 더 넣을 때마다 상태가 변합니다. 이런 시스템들의 공통점은 (1) 가능한 상태들의 집합이 명확하고, (2) 한 상태에서 다른 상태로 가는 규칙이 정해져 있다는 점이에요. 우리가 다루는 알고리즘이나 프로그램도 본질적으로 똑같습니다.
정의 6.1.1 (상태 기계)
상태 기계(state machine)는 다음 세 가지로 구성된 구조 \( M = (Q, q_0, \delta) \)입니다.
(1) 상태 집합 \( Q \) — 가능한 모든 상태들의 모음. 유한해도 되고 무한해도 됩니다.
(2) 시작 상태 \( q_0 \in Q \) — 기계가 처음 놓이는 상태.
(3) 전이 관계 \( \delta \subseteq Q \times Q \) — 한 걸음에 갈 수 있는 (현재 상태, 다음 상태) 쌍의 집합. \( (q, q') \in \delta \)이면 \( q \to q' \)로 씁니다.
전이를 함수로 보지 않고 관계로 정의한 이유는, 같은 상태에서 여러 다음 상태로 갈 수 있는 비결정적(nondeterministic) 시스템도 다루기 위해서예요. 만약 모든 \( q \)에 대해 \( q \to q' \)인 \( q' \)가 정확히 하나뿐이면, 이를 결정적(deterministic) 상태 기계라 부릅니다.
정의 6.1.2 (실행과 도달 가능성)
상태 기계 \( M \)의 실행(execution)은 다음을 만족하는 상태들의 (유한 또는 무한) 수열입니다.
\[ q_0 \to q_1 \to q_2 \to \cdots \]
여기서 \( q_0 \)는 시작 상태이고, 모든 \( i \)에 대해 \( q_i \to q_{i+1} \)이 전이 관계에 속합니다. 어떤 실행에 등장하는 상태 \( q \)를 도달 가능한 상태(reachable state)라고 합니다.
그래프로 그리면 직관이 확 살아나요. 각 상태를 노드로, 전이를 화살표로 표현하면 상태 기계는 방향 그래프가 됩니다. 시작 상태를 진하게 표시하고, 거기서부터 화살표를 따라 갈 수 있는 모든 노드들이 도달 가능한 상태들의 집합이지요.
예제 6.1.3 (간단한 카운터)
0부터 시작해서 매 단계 1씩 올라가는 카운터를 생각합시다. \( Q = \mathbb{N} \), \( q_0 = 0 \), \( \delta = \{ (n, n+1) : n \in \mathbb{N} \} \). 도달 가능한 상태는 \( \{0, 1, 2, \ldots\} = \mathbb{N} \) 전체입니다. 이 기계의 실행은 단 하나, \( 0 \to 1 \to 2 \to \cdots \)뿐이지요.
예제 6.1.4 (충돌 감지 카운터)
이번에는 두 사람이 같은 변수에 1을 더하려는 상황을 모델링해봐요. 상태는 정수 \( n \). 전이는 \( n \to n+1 \) 하나뿐인데, 두 프로세스가 동시에 \( n \)을 읽고 각각 \( n+1 \)을 쓰면 두 번의 증가가 한 번의 증가처럼 보일 수 있습니다. 이런 동시성 버그를 상태 기계로 정밀하게 묘사할 수 있다는 점이 포인트예요.
프로그램을 상태 기계로 보는 시각의 강력함은, "변수들의 현재 값"이라는 추상적 개념을 "상태"라는 수학적 대상으로 끌어올린다는 데 있습니다. 일단 이렇게 모델링하고 나면, 우리는 프로그램의 실행을 그래프 위의 산책으로 바꿔 분석할 수 있어요.
상태 기계가 만들 수 있는 도달 가능한 상태들의 집합은 보통 어마어마하게 큽니다. 모든 상태를 일일이 검사해서 "이 시스템은 절대 나쁜 상태에 빠지지 않는다"고 말할 수는 없죠. 그러면 어떻게 해야 할까요? 답은 5장에서 배운 귀납을 한 번 더 변주하는 데 있습니다. 바로 불변량(invariant)이라는 아이디어예요.
정의 6.2.1 (보존되는 성질)
상태 \( q \)에 대한 성질 \( P(q) \)가 상태 기계 \( M \)에서 보존된다(preserved)는 것은 다음을 의미합니다.
\[ \forall q, q' \in Q \,:\; \big(P(q) \,\wedge\, q \to q'\big) \;\Rightarrow\; P(q'). \]
즉, \( P \)가 성립하는 어떤 상태에서 한 걸음을 가면, 도착한 상태에서도 \( P \)가 여전히 성립한다는 뜻이에요.
정리 6.2.2 (불변량 원리)
성질 \( P \)가 시작 상태에서 성립하고(\( P(q_0) \)이 참), 모든 전이에 대해 보존된다면, \( P \)는 도달 가능한 모든 상태에서 성립합니다.
증명
임의의 도달 가능한 상태 \( q \)를 잡으면, 정의에 의해 어떤 실행 \( q_0 \to q_1 \to \cdots \to q_n = q \)가 존재합니다. 실행의 단계 수 \( n \)에 대해 귀납을 합시다. \( n = 0 \)이면 \( q = q_0 \)이고 가정에 의해 \( P(q_0) \)이 참. \( P(q_k) \)가 참이라 하면, \( q_k \to q_{k+1} \)이고 \( P \)가 보존되므로 \( P(q_{k+1}) \)도 참입니다. 따라서 \( P(q_n) = P(q) \)가 성립.
∎
형식만 보면 5장의 수학적 귀납과 거의 똑같죠? "기저: 시작 상태에서 성립한다", "귀납 단계: 한 걸음 가도 보존된다." 차이는 자연수 위가 아니라 상태 기계의 실행 위에서 귀납을 한다는 점뿐이에요. 그래서 불변량 원리를 실행 귀납(induction on executions)이라고도 부릅니다.
예제 6.2.3 (6×6 보드의 X)
6×6 격자판이 있고, 왼쪽 위 칸에 X 마커가 한 개 놓여 있어요. 한 번의 동작은 X를 한 칸 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 옮기는 것입니다. 질문: 적당히 옮기다 보면 X를 오른쪽 아래 칸으로 보낼 수 있을까요?
답은 "할 수 있습니다"인데, 살짝 변형해 봐요. 만약 매번 X를 옮길 때마다 그 자리에 도장을 찍어서 같은 칸을 두 번 밟지 못한다면? 또는 정확히 35번 움직여서 도착해야 한다면? 이런 문제는 칸을 체스판처럼 흑백으로 칠해 놓고 보면 답이 보입니다.
색깔 불변량: 왼쪽 위를 흰색, 그 옆을 검은색으로 칠하는 식으로 시계판 무늬를 그리면, 한 번 움직일 때마다 X가 놓인 칸의 색은 반드시 바뀝니다. 즉 "X가 놓인 칸의 색깔과 지금까지 움직인 횟수의 홀짝은 항상 같다"는 성질이 보존돼요. 시작 칸이 흰색이고 0번 움직였으면 둘 다 짝수. 35번 움직이면 홀수가 되어 X는 검은 칸에 있어야 합니다. 그런데 오른쪽 아래 칸은? 6+6이 짝수이므로 시작 칸과 같은 색, 즉 흰색이에요. 검은색이 아닙니다. 따라서 정확히 35번 만에 도달하는 것은 불가능합니다.
이 예제의 매력은, 무한히 많은 가능한 경로를 일일이 따져보지 않고도 단 한 줄의 색깔 불변량으로 결론을 내렸다는 점이에요. 좋은 불변량을 찾는 것이 곧 좋은 증명을 찾는 것입니다.
노트
불변량은 너무 약하면 도움이 안 되고, 너무 강하면 보존되지 않아요. "그럴듯해 보이지만 보존되지 않는 성질"을 강화해서 "더 풍성하지만 진짜로 보존되는 성질"로 바꾸는 작업을 불변량 강화(strengthening the invariant)라고 부릅니다. 알고리즘 분석에서 가장 많은 시간이 들어가는 부분이지요.
알고리즘이 "옳다"는 말에는 사실 두 가지 약속이 들어 있습니다. 첫째, 끝날 때 답이 맞아야 한다(부분 정확성, partial correctness). 둘째, 무한히 돌지 않고 언젠가는 끝나야 한다(종료성, termination). 둘은 별개의 문제예요. 영원히 도는 알고리즘은 답을 절대 틀리지 않을 수 있고(왜냐하면 답을 절대 안 내놓으니까), 빨리 끝나는 알고리즘이 엉뚱한 답을 줄 수도 있죠. 그래서 두 가지를 따로 증명합니다.
정의 6.3.1 (부분 정확성과 종료성)
알고리즘을 상태 기계로 모델링했을 때, 종료 상태에 도달했다면 항상 올바른 답이 나오는 성질을 부분 정확성이라 합니다. 어떤 입력에서 출발하든 유한 번의 전이 안에 종료 상태에 도달하는 성질을 종료성이라 합니다. 둘이 모두 성립하면 알고리즘이 전체적으로 정확하다(totally correct)고 말합니다.
부분 정확성은 6.2의 불변량 원리로 증명합니다. "지금까지 계산한 값과 입력 사이에 어떤 관계가 항상 성립한다"는 불변량을 잡고, 이 불변량이 종료 상태에서 정답을 함의하도록 만들면 끝이에요. 종료성은 새 도구가 필요한데, 이름은 variant입니다.
정의 6.3.2 (variant)
상태 기계 \( M \)에 대해 variant는 함수 \( v : Q \to \mathbb{N} \)으로, 모든 비종료 상태 \( q \)와 그 다음 상태 \( q' \)에 대해
\[ v(q') < v(q) \]
를 만족하는 함수입니다. 즉 한 걸음을 갈 때마다 \( v \) 값이 자연수에서 엄격히 감소해요.
정리 6.3.3 (종료 정리)
상태 기계가 자연수 값을 갖는 variant를 가지면, 모든 실행은 유한 단계 안에 종료 상태에 도달합니다.
증명
variant 값은 자연수이므로 음이 될 수 없고, 매 전이마다 엄격히 줄어듭니다. 자연수의 정렬성(well-ordering principle, 5장 참고)에 의해 무한히 줄어드는 자연수 수열은 존재하지 않으므로, 어느 순간 더 이상 전이가 불가능한 상태, 즉 종료 상태에 도달합니다.
∎
예제 6.3.4 (빠른 거듭제곱)
밑 \( a \), 지수 \( n \)에 대해 \( a^n \)을 계산하는 알고리즘을 봅시다.
def fast_pow(a, n):
r = 1
x = a
k = n
while k > 0:
if k % 2 == 1:
r = r * x
x = x * x
k = k // 2
return r
상태는 변수 \( (r, x, k) \)의 값. 시작 상태는 \( (1, a, n) \), 종료 상태는 \( k = 0 \)인 상태.
불변량: \( r \cdot x^k = a^n \). 시작 상태에서 \( 1 \cdot a^n = a^n \)이므로 성립. 한 걸음에서 두 경우를 따져봐요. \( k \)가 홀수인 분기에서는 \( r' = r x \), \( x' = x^2 \), \( k' = (k-1)/2 \). 그러면 \( r' (x')^{k'} = r x \cdot x^{k-1} = r x^k = a^n \). 짝수 분기에서는 \( r' = r \), \( x' = x^2 \), \( k' = k/2 \)이고 \( r' (x')^{k'} = r \cdot x^k = a^n \). 양쪽 모두 보존됩니다.
variant: \( v(r, x, k) = k \). 매 반복에서 \( k \)는 \( (k-1)/2 \) 또는 \( k/2 \)로 줄어들고, 둘 다 \( k \geq 1 \)일 때 엄격히 작아집니다.
종료 시 \( k = 0 \)이므로 불변량은 \( r \cdot x^0 = r = a^n \). 즉 반환값 \( r \)이 정확히 \( a^n \). 부분 정확성과 종료성 모두 한 줄짜리 불변량과 한 줄짜리 variant로 증명됐어요.
예제 6.3.5 (유클리드 알고리즘)
두 양의 정수 \( a, b \)의 최대공약수를 구하는 고전 알고리즘.
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
상태는 \( (a, b) \). 시작 상태는 입력 \( (a_0, b_0) \), 종료는 \( b = 0 \).
불변량: \( \gcd(a, b) = \gcd(a_0, b_0) \). 임의의 \( a, b \)에 대해 \( \gcd(a, b) = \gcd(b, a \bmod b) \)는 잘 알려진 사실이므로 한 걸음마다 보존됩니다.
variant: \( v(a, b) = b \). \( b > 0 \)인 동안 \( a \bmod b < b \)이므로 새 \( b \) 값은 항상 더 작은 자연수입니다.
종료 시 \( b = 0 \)이므로 \( \gcd(a, 0) = a \). 불변량에 의해 이 값이 \( \gcd(a_0, b_0) \)와 같음. 끝!
이 두 예제에서 강조하고 싶은 건, "복잡한 코드를 한 줄씩 따라가며 머리로 시뮬레이션"하지 않는다는 점이에요. 우리는 한 줄짜리 수학적 성질 두 개(invariant + variant)를 잡고 그게 보존되는지만 검사했습니다. 코드가 길어져도 같은 원칙이 그대로 작동하는 게 이 방법의 위력입니다.
노트
variant가 꼭 자연수일 필요는 없어요. 임의의 정렬 집합(well-ordered set), 예를 들어 사전식 순서를 갖는 \( \mathbb{N} \times \mathbb{N} \) 같은 곳에서 값이 줄어들기만 해도 종료 정리가 성립합니다. 하지만 자연수가 가장 자주 쓰이고 가장 직관적이에요.
이제 지금까지 배운 도구를 진짜 알고리즘에 적용해 봅시다. 무대는 다소 낭만적이지만 정작 수학은 차갑고 정확해요. \( n \)명의 남자와 \( n \)명의 여자가 있고, 각자가 모든 이성을 자기 마음대로 1등부터 \( n \)등까지 줄을 세워 둔 선호 순위를 갖고 있습니다. 우리의 임무는 \( n \)쌍의 결혼을 짝지어 주는 것. 단, 결과가 "안정적"이어야 해요. 어떤 의미에서?
정의 6.4.1 (안정 매칭)
매칭 \( M \)이 두 사람 \( B \)(남자)와 \( G \)(여자)에 대해 다음을 모두 만족할 때, \( (B, G) \)를 도주 쌍(rogue couple)이라 합니다.
(1) \( M \)에서 \( B \)는 \( G \)가 아닌 다른 여자와 짝지어졌다.
(2) 그럼에도 \( B \)는 자신의 현재 짝보다 \( G \)를 더 선호한다.
(3) 동시에 \( G \)도 자신의 현재 짝보다 \( B \)를 더 선호한다.
도주 쌍이 단 한 쌍도 존재하지 않는 매칭을 안정(stable)하다고 합니다.
도주 쌍이 있다는 건 두 사람이 동시에 "지금 내 짝보다 너랑이 낫겠다"고 생각한다는 뜻이에요. 그러면 이 둘은 각자의 현재 짝을 버리고 서로에게 도망갈 동기가 충분합니다. 안정 매칭이란 그런 일이 절대 일어나지 않는 매칭이지요. 인기 비유로 말하면 아무도 환승 결혼을 시도할 이유가 없는 상태예요.
두 가지 자연스러운 질문이 떠오릅니다. (1) 어떤 선호 순위가 주어지든 안정 매칭이 항상 존재할까? (2) 존재한다면, 효율적으로 찾을 수 있을까? 둘 다 답은 "예"이고, 그 답을 동시에 주는 것이 1962년 게일과 섀플리(Gale & Shapley)의 알고리즘입니다.
정의 6.4.2 (Gale-Shapley 알고리즘)
이 알고리즘은 매일 아침 한 라운드씩 진행됩니다.
아침: 아직 결혼 약속이 확정되지 않은 모든 남자는 자기 선호 순위에서 아직 거절당하지 않은 여자 중 가장 위에 있는 사람에게 가서 청혼합니다.
점심: 청혼을 받은 여자는, 만약 청혼자가 한 명이면 그 사람을 일단 "보류"(maybe)로 잡아 두고, 여러 명이면 그중 자기 선호 순위에서 가장 높은 사람만 보류로 잡습니다. 이미 어제부터 보류 중이던 사람이 있는데 새 청혼자가 그 사람보다 자기 마음에 더 들면, 어제 보류는 풀고 새 사람으로 갈아탑니다.
저녁: 보류로 선택받지 못한 모든 청혼자는 거절당했다고 기록하고 다음 날 다른 사람에게 청혼할 준비를 합니다.
아침에 청혼할 사람이 아무도 없는 날이 오면 알고리즘은 멈추고, 모든 보류 관계가 결혼으로 확정됩니다.
약간 일방적이고 구식인 설정이지만(실제로 게일·섀플리가 1962년에 쓴 그대로의 비유입니다), 알고리즘의 수학적 성질을 분석하기에는 깔끔해요. 우선 진짜로 끝나긴 하는지부터 확인합시다.
정리 6.4.3 (종료성)
Gale-Shapley 알고리즘은 최대 \( n^2 \)일 안에 종료합니다.
증명
variant로 "거절 횟수의 총합"을 잡습니다. 정확히는, 각 남자마다 그가 아직 청혼해 보지 않은(거절당하지도 않은) 여자의 수를 합한 값을 \( v \)라 합시다. 처음에는 \( v = n \cdot n = n^2 \). 매 라운드에서 적어도 한 명의 남자가 거절당하지 않으면(즉 모두가 보류 상태가 되면) 알고리즘은 끝나고, 한 명이라도 거절당하면 그 사람의 "후보 목록"에서 한 명이 빠지므로 \( v \)는 적어도 1 감소합니다. \( v \)는 자연수이므로 \( n^2 \)번 이내에 0 또는 종료에 도달합니다.
∎
다음으로, 끝났을 때 진짜로 모두가 짝지어지는지를 확인해야 합니다.
보조정리 6.4.4 (보류의 단조성)
일단 어떤 여자가 누군가를 보류로 잡으면, 그 이후로 그녀의 보류 상대는 점점 자기 선호 순위에서 위로 올라가기만 합니다(절대 내려가지 않아요).
이건 알고리즘 정의에서 바로 따라옵니다. 새 청혼자로 갈아탈 때는 무조건 더 마음에 드는 쪽으로만 갈아타니까요. 이 단조성에서 또 하나가 따라 나옵니다.
보조정리 6.4.5 (모두 짝지어진다)
알고리즘이 끝났을 때, 모든 사람은 정확히 한 명의 짝을 갖습니다.
증명
모순으로 가정합시다. 종료 시 짝이 없는 남자 \( B \)가 있다고 해요. 그러면 \( B \)는 \( n \)명의 여자 모두에게 한 번씩 거절당했어야 알고리즘이 종료했을 것입니다(아니면 그는 아직 청혼할 사람이 남아 있어서 종료하지 않을 테니까). 그런데 보조정리 6.4.4에 의해, 한 번이라도 보류를 잡아본 여자는 종료 시점까지 계속 누군가를 보류로 잡고 있어요. 그리고 모든 여자는 \( B \)에게 청혼받은 적이 있으니 모두 한 번 이상 보류 상태였습니다. 따라서 \( n \)명의 여자가 모두 짝을 갖고 있는데, 짝지어진 여자의 수가 \( n \)이면 짝지어진 남자의 수도 \( n \). 그런데 \( B \)는 짝이 없다고 했으니 모순.
∎
이제 가장 중요한 안정성을 증명할 차례예요. 핵심 아이디어는 매혹적일 만큼 단순합니다.
정리 6.4.6 (안정성)
Gale-Shapley 알고리즘이 만들어 내는 매칭은 안정적입니다. 즉 도주 쌍이 존재하지 않습니다.
증명
모순으로 도주 쌍 \( (B, G) \)가 있다고 가정합시다. \( B \)의 짝은 \( G' \neq G \)이고 \( G \)의 짝은 \( B' \neq B \)인데, \( B \)는 \( G \)를 \( G' \)보다 선호하고, \( G \)는 \( B \)를 \( B' \)보다 선호한다고 하지요.
\( B \)는 알고리즘 동안 자기 선호 순위의 위에서부터 청혼합니다. \( B \)에게 \( G \)는 \( G' \)보다 위에 있으므로, \( B \)는 \( G' \)에게 청혼하기 전에 반드시 \( G \)에게 먼저 청혼했을 것입니다. 그런데 \( G \)는 결국 다른 사람 \( B' \)와 짝지어졌어요. 두 가지 가능성이 있습니다. (a) \( G \)가 \( B \)의 청혼을 거절했거나, (b) 잠깐 보류했다가 나중에 다른 사람으로 갈아탔거나. 둘 다 결국 \( G \)는 \( B \)를 버린 것이고, 그건 \( G \)가 그 시점에 더 마음에 드는 다른 청혼자가 있었다는 뜻입니다.
이제 보조정리 6.4.4(보류의 단조성)가 결정타예요. \( G \)가 \( B \)를 버리고 잡은 누군가는 \( B \)보다 위에 있고, 그 후로 \( G \)의 보류 상대는 계속 위로만 올라갔습니다. 따라서 종료 시점의 짝 \( B' \)도 \( B \)보다 위에 있어요. 즉 \( G \)는 \( B' \)를 \( B \)보다 더 선호합니다. 그런데 우리는 \( G \)가 \( B \)를 \( B' \)보다 선호한다고 가정했지요. 모순.
∎
그림으로 정리하면 이래요. \( B \)는 자기 선호 순위의 꼭대기에서부터 차례로 청혼하니까 \( G' \)와 짝이 됐다는 건 \( G \)에게 이미 거절당한 적이 있다는 증거고, 거절당했다는 건 \( G \)에게 그때 더 좋은 사람이 있었다는 증거고, 보류는 단조 증가하니까 종료 시점에는 더 좋아졌으면 좋아졌지 나빠질 수 없다. 한마디로 청혼하는 쪽이 위에서 아래로 내려간다는 사실과, 받는 쪽이 받은 사람들 사이에서 위로 올라간다는 사실이 만나는 지점에서 도주 쌍은 살 자리가 없습니다.
안정성과 종료성에 더해, Gale-Shapley 알고리즘에는 한 가지 흥미로운 성질이 더 있어요.
정리 6.4.7 (청혼자 최적성)
Gale-Shapley 알고리즘이 출력하는 매칭은 청혼자(남자) 입장에서 최적입니다. 즉 모든 남자에 대해, 그 남자가 어떤 안정 매칭에서든 가질 수 있는 가장 선호하는 짝과 짝지어집니다.
증명의 핵심 아이디어만 짚을게요. 어떤 남자 \( B \)가 자기의 "이론상 가능한 최고 짝" \( G \)를 못 받았다고 가정해 봅시다. 즉 알고리즘 진행 중 \( G \)가 \( B \)를 거절하는 첫 번째 순간이 있어요. 그 순간 \( G \)는 \( B \)보다 더 좋은 누군가 \( B^* \)를 보류로 잡고 있었던 거고, 그러면 \( B^* \)도 그 시점까지 자기 선호 순위 위쪽에서 거절당하지 않은 채 \( G \)에게 도달한 거예요. 이 \( B^* \)에게도 \( G \)가 안정 매칭 가능한 짝이라는 가정을 풀어 보면, \( B^* \)의 "이론상 가능한 최고 짝"보다 \( G \)가 위에 있다는 결론이 나오고, 그것을 안정 매칭의 정의와 결합하면 도주 쌍이 만들어져 모순. 즉 "거절당하는 첫 번째 남자"가 존재할 수 없습니다.
노트
대칭적으로 같은 알고리즘은 받는 쪽(여자) 입장에서는 최악입니다. 모든 여자가 어떤 안정 매칭에서든 받을 수 있는 가장 안 좋은 짝을 받게 돼요. 그래서 현실의 매칭 시장(예: 의대 졸업생-병원 배정)에서는 누가 청혼하는 역할을 맡느냐가 매우 중요한 정치적 문제가 됩니다. 게일과 섀플리 그리고 후속 연구로 알 로스(Al Roth)는 이 알고리즘의 변형으로 노벨 경제학상을 받았어요. 사랑 이야기로 시작해서 시장 설계로 끝나는 셈이지요.
이 챕터를 한 줄로 요약하면 이렇게 됩니다. 프로그램은 상태 기계, 옳음의 증명은 불변량, 끝남의 증명은 variant. 도구는 단순하지만 적용 범위는 넓어요. 그리고 그 도구의 뿌리는 결국 5장의 귀납이라는 한 가지 원리입니다. 다음 챕터로 가면 이 도구들이 더 큰 구조 — 그래프와 그 위의 알고리즘 — 에서 어떻게 쓰이는지 보게 될 거예요.