그리디 선택 기준이 안 보이면, 많은 사람이 선택은 떠올리는데 왜 맞는지는 설명하지 못한 채 멈춥니다. 이번 글에서는 애드혹 문제에서 그리디 선택 기준을 어떻게 세우고, 그 기준을 반례로 흔든 뒤, 교환 논증으로 왜 맞는지 설명하는 흐름을 단계적으로 정리해보겠습니다.
왜 그리디는 나중에 막힐까
그리디 문제를 풀다가 막히는 지점은 보통 구현이 아닙니다. 오히려 큰 것부터, 빨리 끝나는 것부터, 지금 손해가 적은 쪽부터 같은 선택 기준이 떠오르는데도 그 기준이 항상 맞는지 확신이 없는 순간에서 멈추게 됩니다. 자연스럽다는 것과 항상 맞다는 것은 다르기 때문입니다.
즉, 그리디는 지금 제일 좋아 보이는 것을 고르는 알고리즘이 아니라 지금 골라도 나중에 최적해를 망치지 않는 선택을 고르는 알고리즘에 가깝습니다. 그래서 예제가 맞는지만 보는 것으로는 부족하고, 그 선택이 미래 선택 공간을 어떻게 바꾸는지도 함께 봐야 합니다.
그리디 선택 기준을 볼 때 먼저 던질 질문
- 지금 고른 선택이 이후 선택 공간을 많이 줄이는가
- 어떤 수치를 작게 유지하면 뒤가 편해지는가
- 최적해와 다른 첫 선택을 해도 서로 바꿔 끼울 수 있는가
첫 번째 질문은 반례를 찾는 데 좋고, 두 번째 질문은 선택 기준을 만드는 데 좋습니다. 세 번째 질문이 바로 교환 논증의 출발점입니다. 예를 들어 구간을 여러 개 고르는 문제라면, 가장 짧은 구간보다 가장 빨리 끝나는 구간이 뒤 선택 공간을 덜 막는지 먼저 봐야 합니다.
그리디가 안 보일수록 지금 좋은 값보다 뒤를 덜 망치는 값을 찾는 것이 중요합니다. 이 감각이 잡히면 기준이 훨씬 빨리 좁혀집니다.
잘못된 기준은 반례에서 먼저 무너진다
구간을 최대한 많이 고르는 문제를 생각해보겠습니다. 겉으로는 시작 시간이 가장 빠른 구간, 길이가 가장 짧은 구간, 끝나는 시간이 가장 빠른 구간이 모두 그럴듯해 보입니다. 하지만 반례를 넣어보면 셋은 같은 무게가 아닙니다.
시작이 빠른 구간부터
- A: [1, 10]
- B: [2, 3]
- C: [3, 4]
- D: [4, 5]
시작 시간이 가장 빠른 구간은 A입니다. 하지만 A를 먼저 고르면 나머지 구간을 거의 못 고릅니다. 결과는 1개입니다. 반면 B, C, D를 고르면 3개를 고를 수 있습니다. 즉, 시작이 빠르다는 기준은 전체 목표와 잘 맞지 않습니다.
길이가 짧은 구간부터
- A: [1, 4]
- B: [4, 7]
- C: [1, 7]
- D: [7, 8]
- E: [8, 9]
길이가 짧은 구간은 매력적으로 보이지만, 짧다는 사실만으로 앞뒤 연결이 최적인지 보장되지는 않습니다. 짧은 구간이더라도 애매한 자리를 차지하면 더 좋은 조합을 막을 수 있습니다. 즉, 짧다는 것은 신호일 수는 있어도 정답 기준이라고 단정하면 위험합니다.
이런 식으로 후보 기준을 반례로 먼저 꺾고 나면, 남는 기준이 왜 더 설득력 있는지 보기 쉬워집니다. 반례를 체계적으로 만드는 흐름은 애드혹 알고리즘 반례 찾는 법 글과도 바로 연결됩니다.
지역 선택은 무엇을 남겨야 할까
그리디 문제에서 좋은 지역 선택은 지금 점수만 큰 선택이 아닙니다. 매 단계에서 무엇을 최대한 남겨야 하는지를 봐야 합니다. 구간 문제라면 보통 뒤에 더 많은 구간이 들어올 수 있는 빈 공간을 남겨야 합니다. 그래서 가장 빨리 끝나는 구간이 강력해집니다.
이 문장을 일반화하면, 지금 이득이 큰 선택보다 나중에 선택 기회를 많이 남기는 선택이 전체 최적해에 더 잘 이어질 수 있다는 뜻입니다. 즉, 그리디의 지역 선택은 눈앞의 점수만 보는 것이 아니라 미래 선택 공간 관리와 연결됩니다.
교환 논증은 왜 필요한가
여기서 많은 사람이 “끝나는 시간이 빠른 게 좋아 보이는 건 알겠는데, 왜 항상 맞죠?”에서 멈춥니다. 바로 이 질문에 답하는 도구가 교환 논증입니다. 교환 논증의 직관은 생각보다 단순합니다. 최적해가 내 첫 선택과 다르더라도, 그 최적해 안의 선택 하나를 내 그리디 선택으로 바꿔도 손해가 없으면 내 선택은 안전하다는 것입니다.
즉, 최적해를 정면으로 부수는 것이 아니라 최적해를 조금 바꿔도 여전히 최적이라는 사실을 보여주는 방식입니다. 핵심은 바꿔 끼운 뒤에도 다음 선택들이 깨지지 않아야 한다는 점입니다. 그래서 교환 논증은 내 선택이 더 좋아 보인다가 아니라 내 선택으로 바꿔도 나머지 구조가 망가지지 않는다를 보여주는 작업입니다.
교환 논증 직관: 회의실 배정 예시
대표 예시로 겹치지 않는 구간을 최대한 많이 고르는 문제를 보겠습니다. 정답 전략은 끝나는 시간이 가장 빠른 구간을 먼저 고르는 것입니다. 먼저 그리디는 가장 빨리 끝나는 구간 G를 고릅니다. 그런데 어떤 최적해 O는 G가 아니라 다른 구간 X로 시작한다고 해보겠습니다.
여기서 중요한 관찰은 G가 가장 빨리 끝나는 구간이므로 end(G) <= end(X)라는 점입니다. 그러면 O의 첫 구간 X를 G로 바꿔도 뒤에 오던 구간들은 여전히 들어올 가능성이 유지됩니다. G가 더 늦게 끝나는 것이 아니라 같거나 더 일찍 끝나기 때문입니다. 즉, X를 G로 바꿔도 구간 개수는 줄지 않습니다.
그렇다면 G로 시작하는 최적해도 하나 존재합니다. 여기까지 오면 첫 선택은 안전하다는 것이 증명됩니다. 그다음에는 G 이후에 남은 부분 문제에서도 같은 논리를 반복하면 됩니다. 이것이 교환 논증의 가장 전형적인 모양입니다.
- 최적해가 내 선택으로 시작하지 않아도 된다
- 대신 첫 선택만 바꿔도 최적성이 유지되면 된다
- 그러면 내 선택으로 시작하는 최적해가 있다고 말할 수 있다
언제 교환 논증 냄새가 날까
- 해가 여러 선택의 순서로 만들어진다
- 첫 선택이 이후 가능 선택에 영향을 준다
- 어떤 기준이 더 일찍 비우거나 덜 막는다고 설명된다
- 최적해의 첫 선택을 바꿔도 나머지 구조가 유지될 것 같다
대표적으로 회의실 배정처럼 구간을 많이 고르는 문제, 마감이나 소요시간을 기준으로 순서를 잡는 문제, 비용이나 시간을 앞으로 당겨 미래 여유를 남기는 문제가 그렇습니다. 반대로 선택 하나가 이후 상태를 너무 복잡하게 바꾸거나 단순 교환으로 구조가 유지되지 않는다면 그리디보다 DP나 완전탐색 쪽이 더 자연스러울 수 있습니다. 이 판단 기준은 그리디로 풀릴까 완전탐색이 필요할까 글과도 연결됩니다.
코드 전에 손으로 확인할 것
- 그럴듯한 기준을 2개 이상 적는다
- 각 기준에 반례를 넣어본다
- 남은 기준이 무엇을 덜 막는지 한국어로 쓴다
- 최적해의 첫 선택을 바꿔도 되는지 상상한다
- 그다음에야 구현한다
이 순서를 거치면 왜 이 정렬 기준인지가 선명해집니다. 애드혹 문제 접근 흐름 전체는 애드혹 문제 풀이법: 규칙 찾기, 반례 만들기, 손으로 먼저 풀어보는 이유 글과 함께 보면 더 잘 이어집니다.
대표 코드: 끝나는 시간이 빠른 구간부터
아래 코드는 회의실 배정 계열에서 가장 기본이 되는 구현입니다. 핵심은 코드 자체보다 왜 끝나는 시간 오름차순으로 정렬하는지가 먼저 이해돼야 한다는 점입니다.
intervals = [(1, 4), (2, 3), (3, 5), (4, 6), (5, 7)]
intervals.sort(key=lambda x: (x[1], x[0]))
count = 0
last_end = -1
selected = []
for start, end in intervals:
if start >= last_end:
selected.append((start, end))
last_end = end
count += 1
print(count)
print(selected)이 코드가 하는 일은 단순합니다. 가장 빨리 끝나는 구간부터 보고, 현재 마지막으로 고른 구간과 겹치지 않으면 선택하고, 선택할 때마다 끝나는 시점을 갱신합니다. 하지만 진짜 핵심은 가장 빨리 끝나는 구간을 먼저 고르면 뒤에 올 수 있는 구간의 선택 공간을 가장 넓게 남기기 쉽다는 문장입니다. 이 문장이 이해되면 코드도 자연스럽게 따라옵니다.
그리디가 안 보일 때 쓰는 체크리스트
- 지금 선택이 미래 공간을 얼마나 막는가
- 무엇을 가장 작게 유지하면 뒤가 편해지는가
- 경쟁 기준 두세 개를 만들 수 있는가
- 그 기준 중 하나를 반례로 바로 깨뜨릴 수 있는가
- 최적해의 첫 선택을 내 선택으로 바꿔도 손해가 없을 것 같은가
여기서 마지막 질문이 특히 중요합니다. 그 질문에 그럴 것 같다가 아니라 왜 그런지 말할 수 있다까지 가면, 교환 논증의 절반은 이미 끝난 상태입니다.
마무리
그리디 교환 논증은 처음부터 수식으로 들어가면 어렵습니다. 하지만 순서를 바꾸면 훨씬 쉬워집니다. 먼저 선택 기준을 세우고, 그 기준을 반례로 흔들어보고, 마지막에 최적해와 바꿔 끼워도 괜찮은지를 보면 됩니다. 즉, 애드혹 문제에서 그리디가 안 보일 때 필요한 것은 번뜩이는 감보다 선택 기준을 검증하는 절차입니다.
관련해서 내부 글로는 그리디로 풀릴까 완전탐색이 필요할까, 애드혹 알고리즘 반례 찾는 법, 애드혹 문제 풀이법: 규칙 찾기와 반례를 함께 읽어보면 좋습니다. 외부 참고로는 구간 스케줄링을 설명하는 Greedy Algorithms 강의 자료와 스케줄링 계열 그리디 예시를 정리한 cp-algorithms의 scheduling 문서가 도움이 됩니다.
