그리디: 지금 가장 좋아 보이는 것을 고르기
거스름돈을 줄 때 큰 동전부터 집습니다. 회의실을 잡을 때 빨리 끝나는 회의부터 넣습니다. 걸음마다 지금 가장 좋아 보이는 것을 고르는 방법, 그리디입니다. 빠르고 쉽지만 늘 맞지는 않습니다. 한 걸음씩 따라가며 맞을 때와 틀릴 때를 비교해 보세요.
한 줄 답. 그리디는 걸음마다 지금 가장 좋아 보이는 것 하나를 고르고, 고른 것은 되돌리지 않는 방법입니다. 갈래 하나만 따라가서 빠릅니다. 대신 늘 맞지는 않습니다. 맞는지는 탐욕적 선택 속성(greedy-choice property), 곧 「지금의 가장 좋은 선택이 전체의 가장 좋은 답 안에 들어 있는가」로 갈립니다. 틀리는 예를 하나라도 찾으면 그 그리디는 틀린 것입니다.
「다음」을 누르면 한 걸음씩 나아갑니다. 동전 하나를 고르는 데 두 걸음이 듭니다. ① 비교하기: 남은 금액과 동전을 양쪽 화살표로 잇고 오른쪽 위에 500 ≤ 760 같은 식을 적습니다. 들어가는 가장 큰 동전은 주황, 남은 금액보다 커서 건너뛴 동전은 흐리게 긋습니다. ② 내기: 고른 동전이 화살표를 따라 「낸 동전」 줄로 옮겨 가고, 오른쪽 위에 760 − 500 = 260 같은 뺄셈이 나옵니다. 「낸 동전」 줄(초록)은 그리디가 지금까지 낸 동전, 아래 줄(파랑)은 모든 경우를 따져 찾은 가장 적은 답입니다. 그리디가 더 많이 쓰면 끝 걸음에 아래 줄의 빈자리를 점선으로 그리고 「1개 더」처럼 적습니다. 금액은 「500, 100, 50, 10」 묶음에서 10 ~ 2000(10 단위), 「4, 3, 1」 묶음에서 1 ~ 30 입니다.
해 볼 것. ① 처음 금액 760 은 동전 다섯 개(500, 100, 100, 50, 10)로 끝납니다. 동전마다 비교하기와 내기 두 걸음이라 모두 10 걸음이고, 아래 줄의 가장 적은 답도 5개입니다. ② 「4, 3, 1」 을 누르면 금액이 6 이 됩니다. 그리디는 4, 1, 1 로 3개를 쓰고, 가장 적은 답은 3 + 3 의 2개입니다. ③ 같은 묶음에서 금액을 10 으로 바꾸면 그리디는 4 + 4 + 1 + 1(4개), 가장 적은 답은 4 + 3 + 3(3개)입니다. ④ 「500, 100, 50, 10」 에서는 두 줄의 개수가 늘 같습니다. 이 쪽의 자가 검사가 10 ~ 2000 을 10 단위로 모두 비교해 확인합니다.
1. 그리디란: 지금 가장 좋은 것을 고르고 뒤돌아보지 않기
그리디는 문제를 걸음으로 나눠 풉니다. 걸음마다 하는 일은 셋입니다.
1. 아직 보지 않은 것 가운데, 정한 기준으로 지금 가장 좋아 보이는 것 하나를 고른다
2. 넣어도 규칙에 어긋나지 않으면 넣고, 어긋나면 버린다
3. 다 볼 때까지 1 로 돌아간다. 한 번 넣거나 버린 것은 다시 보지 않는다
거스름돈에서 기준은 「남은 금액에 들어가는 가장 큰 동전」이고, 규칙은 「남은 금액을 넘지 않기」입니다. 회의실에서 기준은 「빨리 끝나는 것」(실험 ② 에서 다른 기준으로 바꿔 봅니다)이고, 규칙은 「이미 넣은 회의와 겹치지 않기」입니다.
그리디는 앞날을 보지 않습니다. 지금 고른 것이 나중에 어떤 결과를 낳을지 따지지 않고, 되돌아가서 다른 갈래를 해 보지도 않습니다. 그래서 빠릅니다. 회의실 문제는 회의를 한 번 줄 세우고(정렬) 위에서부터 한 번 훑으면 끝납니다. 그리고 같은 까닭으로 틀릴 수 있습니다. 앞에서 고른 것 때문에 더 좋은 답으로 가는 길이 막혀도 알아채지 못합니다.
2. 손으로 따라가기
실험 ① 의 처음 값, 금액 760 을 동전 500, 100, 50, 10 으로 만듭니다.
| 고른 차례 | 남은 금액 | 들어가는 가장 큰 동전(왜) | 고른 뒤 남은 금액 | 지금까지 고른 동전 |
|---|---|---|---|---|
| 1 | 760 | 500(500 ≤ 760) | 760 − 500 = 260 | 500 |
| 2 | 260 | 100(500 > 260 이라 건너뜀, 100 ≤ 260) | 260 − 100 = 160 | 500, 100 |
| 3 | 160 | 100(500 > 160 이라 건너뜀, 100 ≤ 160) | 160 − 100 = 60 | 500, 100, 100 |
| 4 | 60 | 50(500, 100 > 60 이라 건너뜀, 50 ≤ 60) | 60 − 50 = 10 | 500, 100, 100, 50 |
| 5 | 10 | 10(500, 100, 50 > 10 이라 건너뜀, 10 ≤ 10) | 10 − 10 = 0 | 500, 100, 100, 50, 10 |
동전 5개입니다. 모든 경우를 따져도 5개보다 적게는 만들 수 없습니다. 이 묶음과 이 금액에서는 그리디가 맞았습니다.
이번에는 지어낸 동전 4, 3, 1 로 금액 6 을 만듭니다.
- 남은 6: 들어가는 가장 큰 동전은 4. 남은 2.
- 남은 2: 4 와 3 은 커서 건너뛰고 1. 남은 1.
- 남은 1: 1. 남은 0. 그리디의 답은
4 + 1 + 1, 동전 3개.
그런데 3 + 3 이면 2개로 됩니다. 첫 걸음에서 지금 가장 커 보이는 4 를 고른 순간, 남은 2 는 1 + 1 로밖에 채울 수 없게 됐습니다. 그리디는 되돌아가지 않으니 이것을 고치지 못합니다.
3. 맞는 문제와 틀리는 문제
그리디가 맞는지를 가르는 물음은 탐욕적 선택 속성 하나입니다. 「지금 가장 좋아 보이는 선택이, 전체의 가장 좋은 답 가운데 적어도 하나 안에 들어 있는가?」 들어 있다면 그것을 고르고 남은 작은 문제를 같은 방법으로 풀어도 손해가 없습니다. 걸음마다 이것이 참이면 그리디는 끝까지 맞습니다. 4, 3, 1 로 6 을 만들 때 첫 선택 4 는 가장 좋은 답 3 + 3 안에 없습니다. 그래서 틀렸습니다.
아래 실험은 같은 물음을 회의실에 던집니다. 회의실은 하나이고 지어낸 회의가 8개 있습니다. 겹치지 않게 가장 많이 넣고 싶습니다. 고르는 기준을 바꿔 보세요.
줄 세운 차례로 회의 하나를 두 걸음에 봅니다. ① 비교하기: 이번에 보는 회의에 주황 굵은 테와 「지금」 화살표가 붙고, 이미 넣은 회의 가운데 가장 가까운 것(겹치면 겹친 것)이 주황 점선 테가 됩니다. 먼저 시작하는 회의의 끝과 나중 회의의 시작에 세로 점선을 내리고, 그림 아래에 끝 ≤ 시작이면 「안 겹침」, 끝 > 시작이면 「겹침」이라고 적습니다. ② 정하기: 안 겹치면 초록 바탕에 「넣음」, 겹치면 흐리게 「겹침」입니다. 한 회의가 끝나는 시각에 다음 회의가 바로 시작하는 것은 겹치지 않는다고 봅니다. 기준이 같은 회의(길이가 같은 회의 등)는 먼저 시작하는 것부터 봅니다.
해 볼 것. ① 「빨리 끝나는 것부터」는 B, C, E, F, H 를 넣어 5개입니다. 모든 경우(256 가지 묶음)를 따진 가장 많은 수도 5개입니다. ② 「빨리 시작하는 것부터」는 9:00 에 시작하는 긴 회의 A 를 먼저 넣습니다. A 가 13:30 까지 방을 차지해 B, C, D, E 가 모두 빠지고 3개(A, F, H)입니다. ③ 「짧은 것부터」는 한 시간짜리 D 와 G 를 먼저 넣는데, D 는 C·E 둘과, G 는 F·H 둘과 겹칩니다. 3개(D, G, B)입니다.
물음을 던져 봅니다. 「빨리 시작하는 것부터」의 첫 선택 A 를 넣으면 많아야 3개입니다. A 와 겹치지 않는 회의가 F, G, H 뿐이기 때문입니다. 「짧은 것부터」의 첫 선택 D 를 넣으면 많아야 4개입니다. 둘 다 첫 걸음에서 이미 가장 좋은 답(5개) 밖으로 나갔습니다. 「빨리 끝나는 것부터」의 첫 선택 B 는 가장 좋은 답 B, C, E, F, H 안에 있습니다.
「빨리 끝나는 것부터」는 이 쪽의 입력에서 맞았고, 이 기준이 어떤 회의 목록에서도 가장 많은 수를 준다는 것이 알려져 있습니다. 느낌으로는, 가장 먼저 끝나는 회의를 넣으면 뒤에 남는 시간이 가장 깁니다. 왜 늘 맞는지의 증명은 이 쪽에서 다루지 않습니다.
반례 하나면 그 그리디는 틀린 것
그리디를 만들었으면 맞다는 것을 증명하거나, 틀리는 예(반례, counterexample)를 찾아야 합니다. 예를 백 번 돌려 다 맞아도 증명이 아닙니다. 「짧은 것부터」도 회의가 띄엄띄엄 놓인 날에는 맞을 수 있습니다. 하지만 D, G 처럼 짧은 회의가 두 회의 사이에 걸친 예가 하나라도 있으면 그 기준은 틀린 것입니다. 틀리는 예를 찾는 쉬운 길은 작은 입력을 만들어 모든 경우를 따진 답과 비교하는 것입니다. 이 쪽의 자가 검사도 「500, 100, 50, 10」 에서 금액 200 가지를 모두 이렇게 비교합니다.
4. 꼭 알아야 할 성질
| 성질 | 쉬운 말 | 실험에서 |
|---|---|---|
| 되돌아가지 않는다 | 한 번 넣거나 버린 것은 다시 보지 않는다 | 6 에서 4 를 고른 뒤 고치지 못한다 |
| 빠르다 | 갈래 하나만 따라간다. 회의실은 정렬 한 번과 훑기 한 번 | 회의 8개를 한 번씩 보고 끝낸다(실험은 비교하기와 정하기로 나눠 16 걸음) |
| 늘 맞지는 않다 | 지금 좋아 보이는 것이 전체로는 손해일 수 있다 | 4, 3, 1 의 6, 「짧은 것부터」 |
| 맞는지는 문제와 기준에 달렸다 | 같은 거스름돈이라도 동전 묶음에 따라, 같은 회의실이라도 기준에 따라 갈린다 | 두 동전 묶음, 세 기준 |
| 맞다는 것은 증명으로, 틀리다는 것은 예 하나로 | 많이 돌려 맞아도 증명이 아니다. 틀리는 예는 하나면 충분하다 | 자가 검사의 200 가지 비교 |
5. 코드로
def greedy_change(amount, coins):
taken = []
for coin in sorted(coins, reverse=True): # 큰 동전부터
while amount >= coin:
taken.append(coin)
amount -= coin
return taken
def most_meetings(meetings): # (시작, 끝) 목록
picked, last_end = [], float("-inf")
for start, end in sorted(meetings, key=lambda m: m[1]): # 빨리 끝나는 것부터
if start >= last_end: # 끝나는 시각에 시작해도 된다
picked.append((start, end))
last_end = end
return picked
greedy_change(6, [4, 3, 1]) 은 [4, 1, 1] 을 돌려줍니다. 그리디의 기준은 sorted(..., key=...) 한 줄에 들어 있습니다. 기준을 바꾸려면 key 만 바꾸면 됩니다(key=lambda m: m[0] 이면 빨리 시작하는 것부터). Python 표준 라이브러리에 그리디 자체는 없습니다.
6. 언제 무엇을 쓰나
| 방법 | 하는 일 | 걸리는 시간(가장 좋을 때 · 보통 · 가장 나쁠 때) | 더 드는 메모리 | 좋은 점 · 나쁜 점 · 쓰는 경우 |
|---|---|---|---|---|
| 그리디 | 걸음마다 지금 가장 좋은 것 하나를 고르고 되돌아가지 않는다 | 회의실: 셋 다 O(n log n). 정렬이 대부분이라 회의가 두 배면 두 배 조금 넘게 | 고른 것을 담을 자리, O(n) | 빠르고 짧다. 틀릴 수 있다. 맞는다고 알려진 문제(회의실 배정, 최소 신장 트리, 다익스트라)에 쓴다 |
| 동적 계획법 | 작은 문제의 답을 표에 모두 적고, 그 위에서 큰 문제의 가장 좋은 답을 고른다 | 거스름돈: 셋 다 O(금액 × 동전 종류 수). 금액이 두 배면 두 배 | 금액마다 칸 하나, O(금액) | 그리디가 틀리는 거스름돈도 맞게 푼다. 표가 커질 수 있다. 작은 답을 모아 큰 답을 만드는 문제에 쓴다 |
| 백트래킹 | 모든 갈래를 따라가 보되, 안 될 갈래는 일찍 접는다 | 회의실: 가장 나쁠 때 O(2ⁿ), 회의가 하나 늘면 두 배. 일찍 접는 갈래가 많으면 훨씬 적다 | 지금 따라가는 갈래 하나, O(n) | 늘 맞다. 입력이 커지면 감당할 수 없다. 입력이 작을 때, 그리디의 답을 시험할 때 쓴다 |
빅오 표기는 시간 복잡도 쪽에서 다룹니다. n 은 회의의 수입니다. 이 쪽의 「모든 경우를 따진 값」은 회의 8개의 묶음 256 가지(2⁸)를 모두 보는 가장 단순한 방법으로 구했습니다.
어디에 쓰나
- 회의실·강의실 배정, 일정 잡기. 빨리 끝나는 것부터 넣습니다.
- 거스름돈. 동전 묶음이 그리디가 맞는 꼴일 때만 씁니다. 묶음이 정해져 있지 않으면 동적 계획법으로 풉니다.
- 최소 신장 트리. 모든 점을 가장 짧은 선의 합으로 잇는 문제입니다. 걸음마다 규칙이 허락하는 가장 짧은 선을 고르는 그리디로 풉니다(최소 신장 트리, 출처).
- 가장 짧은 길. 다익스트라는 걸음마다 아직 확정하지 않은 곳 가운데 가장 가까운 곳을 확정합니다. 길의 길이가 음수가 아닐 때 맞습니다.
- 그리디가 안 맞을 때. 작은 답을 모아 큰 답을 만들 수 있으면 동적 계획법, 입력이 작으면 백트래킹으로 모든 경우를 따집니다.
자주 묻는 것
그리디가 맞는지 어떻게 아나요?
증명해야 압니다. 예를 많이 돌려서 다 맞아도 증명은 아닙니다. 거꾸로 틀리는 예를 하나만 찾으면 그 그리디는 틀린 것입니다. 작은 입력에서 모든 경우를 따지는 방법과 비교하면 틀리는 예를 찾기 쉽습니다. 이 쪽의 자가 검사도 그렇게 비교합니다.
500, 100, 50, 10 동전은 그리디로 늘 되나요?
이 쪽의 코드로 10 ~ 2000(10 단위)의 금액 200 가지를 모두 따져 보니 그리디와 가장 적은 답이 늘 같았습니다. 이 범위 밖과 증명은 이 쪽에서 다루지 않습니다. 동전 묶음이 바뀌면 다시 따져야 합니다. 4, 3, 1 처럼 금액 6 에서 바로 틀리는 묶음이 있습니다.
그리디와 동적 계획법은 어떻게 다른가요?
그리디는 갈래 하나만 따라갑니다. 동적 계획법은 작은 문제의 답을 모두 적어 두고 그 가운데 가장 좋은 것을 고릅니다. 4, 3, 1 로 6 을 만들 때, 동적 계획법은 동전 4, 3, 1 을 하나씩 써 보고 남는 2, 3, 5 의 답(각각 2개, 1개, 2개)을 모두 봅니다. 가장 적은 것은 3 의 1개라서, 동전 3 하나를 더해 2개가 답입니다. 그리디는 4 를 쓰고 남는 2 만 봅니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 지금 가장 좋아 보이는 것을 고르는 방법 | 그리디 알고리즘, 탐욕 알고리즘(greedy algorithm) |
| 걸음마다 고르는 것 | 탐욕적 선택(greedy choice) |
| 전체의 가장 좋은 답 | 최적해(optimal solution) |
| 지금의 선택이 가장 좋은 답 안에 들어 있다 | 탐욕적 선택 속성(greedy-choice property) |
| 틀리는 예 | 반례(counterexample) |
| 모든 경우를 따지기 | 완전 탐색, 브루트 포스(exhaustive search, brute force) |
| 거스름돈 문제 | 동전 교환 문제(coin change problem) |
| 회의실 하나에 회의를 가장 많이 넣기 | 활동 선택 문제, 구간 스케줄링(activity selection, interval scheduling) |
| 모든 점을 가장 짧게 잇는 선들 | 최소 신장 트리(minimum spanning tree, MST) |
출처
- Algorithms, 4th Edition: 4.3 Minimum Spanning Trees. 최소 신장 트리를 그리디로 푸는 본보기(프림, 크루스칼).