그리디 알고리즘은 짜기는 쉽지만 믿기는 어렵다. 매 순간의 욕심이 어떻게 전체 최적으로 이어지는가? 교환논법(exchange argument)은 이 의심에 답하는 표준 기법이다. 임의의 최적해를 가정하고, 그것을 그리디해와 다른 첫 지점에서 "교환"해 그리디해 쪽으로 한 걸음 옮겨도 해가 나빠지지 않음을 보인다. 이 페이지는 그 일반 틀을 세우고, Expert 문제들이 그것을 어떻게 적용하는지 추적한다.
그리디 알고리즘은 "지금 이 순간 가장 좋아 보이는 선택"을 되돌아보지 않고 확정해 나간다. 빠르고 단순하지만, 그 국소적 욕심이 전역 최적과 일치한다는 보장은 공짜로 주어지지 않는다.
그리디가 옳으려면 두 성질이 동시에 성립해야 한다. 첫째는 greedy choice property — 어떤 최적해에든 "그리디가 첫 번째로 고르는 그 선택"이 포함되도록 만들 수 있다는 것. 둘째는 optimal substructure — 첫 선택을 떼어내고 남은 부분문제의 최적해를, 떼어낸 선택과 이으면 원래 문제의 최적해가 된다는 것. 첫째 성질이 보장되면 그리디의 매 단계를 같은 논리로 귀납할 수 있고, 둘째 성질이 그 귀납을 떠받친다.
교환논법은 바로 이 첫째 성질을 증명하는 도구다. 발상은 이렇다 — 그리디해 G와 다른 임의의 최적해 O가 있다 하자. 둘이 처음으로 갈라지는 지점을 찾는다. 그 지점에서 O가 고른 원소를 G가 고른 원소로 바꿔치기(swap)한다. 이 교환이 O를 나쁘게 만들지 않음을 보이면, "그리디 선택을 포함하는 최적해가 존재한다"가 증명된다. 갈라지는 지점이 사라질 때까지 이 논리를 반복하면 O는 결국 G가 되고, 따라서 G 자신이 최적이다.
왜 "교환해도 나빠지지 않는다"가 핵심인가? 그 답이 §2의 일반 틀이다.
구체적인 문제를 떠나, 교환논법이 증명을 만들어내는 골격을 형식화하자. 거의 모든 그리디 정당성 증명이 이 네 단계의 변주다.
cost(O') ≤ cost(O)(최소화 문제) 또는 value(O') ≥ value(O)(최대화 문제)를 보인다. 교환이 해의 실현 가능성(feasibility)도 깨지 않아야 한다.
cost(O') ≤ cost(O)이므로 O'도 최적이다. 그런데 O'은 G와 적어도 k번째 자리까지 일치한다 — 분기점이 한 칸 뒤로 밀렸다. 이 논리를 반복하면 분기점이 끝까지 밀려 O' = G가 되고, 따라서 G가 최적이다.
문제가 다음을 만족한다고 하자. (1) 해는 원소의 수열/집합이다. (2) 그리디 선택 규칙이 만드는 어떤 부등식에 의해, 임의의 실현 가능한 해에서 "그리디가 우선하는 원소"와 "그렇지 않은 원소"를 맞바꾸면 목적함수가 나빠지지 않으며 실현 가능성이 유지된다. 그러면 그리디 알고리즘은 최적해를 산출한다.
최적해 O 중에서 그리디해 G와 가장 긴 공통 접두사(prefix)를 가지는 것을 하나 고른다. 공통 접두사 길이를 k라 하자.
만약 k가 해의 전체 길이라면 O = G이고, O가 최적이므로 G도 최적이다 — 증명 끝.
그렇지 않다면 gₖ₊₁ ≠ oₖ₊₁. 가정 (2)에 의해 O에서 oₖ₊₁을 gₖ₊₁로 교환한 O'은 실현 가능하고 cost(O') ≤ cost(O). O가 최적이므로 O'도 최적이다. 그런데 O'은 G와 공통 접두사 길이가 k+1 이상 — O가 "가장 긴 공통 접두사"라는 선택에 모순. 따라서 첫 경우만 가능하고, G는 최적이다.
교환논법으로 정당화되는 그리디는 대부분 같은 형태를 가진다 — 어떤 키로 원소를 정렬하고, 정렬 순서대로 훑으며 실현 가능하면 선택에 넣는다. 정렬 비교 함수가 곧 "그리디 선택 규칙"이고, 교환논법은 "이 비교 함수로 인접한 두 원소를 swap하면 목적함수가 나빠진다"를 보임으로써 정렬 키의 정당성을 증명한다.
아래는 가장 흔한 두 패턴 — 마감시한 작업 스케줄링(이익 최대화)과 구간 선택(개수 최대화) — 을 하나의 골격으로 보인 것이다.
#include <vector>#include <algorithm>using namespace std;// ── 패턴 A: 구간 선택 — 겹치지 않는 최대 개수 ──// 교환논법: '끝나는 시각이 가장 이른' 구간을 먼저 고른다.// swap 근거: 최적해의 첫 구간을 더 일찍 끝나는 구간으로// 바꿔도 남는 자원이 더 많아져 feasibility가 유지된다.struct Iv { int s, e; };int maxNonOverlap(vector<Iv> v) { sort(v.begin(), v.end(), [](const Iv& a, const Iv& b){ return a.e < b.e; }); int cnt = 0, lastEnd = -1; for (const auto& x : v) { if (x.s >= lastEnd) { // feasible: 선택 ++cnt; lastEnd = x.e; } } return cnt;}// ── 패턴 B: 마감시한 작업 스케줄링 — 이익 최대화 ──// 교환논법: 이익이 큰 작업부터, 마감 이전 가장 늦은 빈 슬롯에.// swap 근거: 인접한 두 작업의 우선순위를 뒤바꾸면// 더 큰 이익이 마감을 놓쳐 목적함수가 손해를 본다.struct Job { int profit, deadline; };long long maxProfit(vector<Job> v, int T) { sort(v.begin(), v.end(), [](const Job& a, const Job& b){ return a.profit > b.profit; // 그리디 키 }); vector<bool> slot(T + 1, false); long long total = 0; for (const auto& j : v) { // 마감 직전부터 비어 있는 슬롯을 역탐색 for (int t = min(T, j.deadline); t >= 1; --t) { if (!slot[t]) { slot[t] = true; total += j.profit; break; } } } return total;}
sort로 그리디 키를 강제하고, 한 번의 선형 스캔으로 feasible할 때만 선택에 담는다. 정렬이 O(n log n), 스캔이 패턴 A는 O(n), 패턴 B는 슬롯 역탐색 때문에 O(nT)(Union-Find로 빈 슬롯을 추적하면 O(n α(T))로 줄어든다 — Union-Find 참고). 코드에서 교환논법은 보이지 않는다 — 그것은 정렬 비교 함수가 "왜 이 키인가"를 정당화하는, 코드 바깥의 증명이다. 비교 함수를 잘못 고르면 컴파일은 되지만 답이 틀린다. 그래서 그리디는 "구현"보다 "증명"이 어렵다.
정렬 기반 그리디의 정당성은 인접한 두 원소의 교환만 따져도 된다. 임의의 두 원소를 맞바꾸는 일은 인접 교환의 연속(버블 정렬과 같다)으로 분해되며, 각 인접 교환이 손해를 내지 않으면 전체 교환도 손해를 내지 않는다. 따라서 "정렬 키가 옳은가"는 곧 "이웃한 두 원소의 우선순위를 뒤집으면 목적함수가 나빠지는가"라는 국소 질문으로 환원된다 — 이것이 비교 함수를 설계하고 검증하는 실전 도구다.
Expert 문제에서 그리디는 교과서의 "구간 선택"으로 곱게 등장하지 않는다. 거의 항상 그리디 선택의 우선순위 키를 문제에서 합성하거나, 그리디가 단독으로는 불완전해 다른 기법과 결합한다. 그래도 정당성의 뿌리는 언제나 교환논법이다.
로봇청소기의 그리디는 매 단계 "1보(one step) 앞을 내다보고 가장 이득이 큰 행동"을 고른다. 핵심은 "이득"을 무엇으로 정의하느냐이다 — 새로 청소되는 칸 수만 보면 근시안적이고, 회전 비용·이동 비용을 함께 합성해야 한다. 교환논법으로 "두 행동의 순서를 뒤바꾸면 합성 이득이 손해를 본다"를 보이는 순간, 그 합성 키가 정당화된다. 키를 잘못 합성하면 그리디는 멀쩡히 돌지만 점수를 잃는다.
안테나배정의 그리디는 가장 외진 UE(user equipment)부터 안테나에 배정한다. 직관은 이렇다 — 외진 UE는 선택지가 적어, 나중으로 미루면 배정할 안테나가 남지 않을 위험이 크다. 교환논법으로 옮기면, "외진 UE를 가까운 UE보다 늦게 배정한 최적해가 있다면, 둘의 배정 순서를 swap해도 손해가 없다(오히려 feasibility가 개선된다)"가 된다. 제약이 많은 원소를 먼저라는 이 발상은 그리디 키 설계의 단골 패턴이다.
TV 화질 최적화는 순수 그리디가 최적을 보장하지 못하는 경우다. 이때 α-greedy — 확률 α로는 그리디 선택을, 1−α로는 무작위/차선 선택을 섞는 — 를 써서 그리디의 국소 함정을 빠져나온다. 교환논법은 여기서 "그리디 선택이 옳다"가 아니라 "그리디 선택이 대개 옳다 — 그래서 높은 확률로 따를 가치가 있다"는 약한 형태의 보장만 준다. 순수 교환논법이 실패하는 지점이 바로 국소탐색이 시작되는 지점이다.
| 기법 | 적용 형태 | 증명 부담 | 쓰임 |
|---|---|---|---|
| Exchange (swap) | 수열·집합 해 | 국소(인접 교환) | 스케줄링·정렬형 — 가장 범용 |
| Stays-ahead | 단조 증가 부분해 | 귀납 | 구간 선택·도달 거리형 |
| Matroid 이론 | 독립집합 구조 | 구조 검증 무거움 | 그리디가 통하는 문제의 추상적 분류 |
| Cut property | 그래프 신장트리 | 국소(컷) | MST — Kruskal·Prim의 정당성 |
| DP (대조군) | 중복 부분문제 | — | 그리디 증명이 실패할 때의 안전한 대안 |
교환논법과 stays-ahead는 같은 진리의 두 표현이다 — 전자는 "최적해를 그리디로 변형"하고, 후자는 "그리디가 최적을 추월하지 않는다"를 직접 보인다. matroid 이론은 한 단계 위의 추상화로, "그리디가 통하는 문제는 정확히 matroid 구조를 가진 문제"라는 깔끔한 분류를 준다 — Kruskal의 MST가 그래픽 matroid 위의 그리디인 것이 대표 예다. 그리디 교환논법으로 정당화되는 MST의 cut property는 Union-Find가 떠받치는 Kruskal 알고리즘의 정확성 그 자체다. 그리고 교환논법이 끝내 막히면 — 그것이 DP 또는 국소탐색으로 넘어갈 시점이다.