그리디 · Hong-Iron

요약

갈림길마다 지금 가장 좋아 보이는 길을 고르고, 한 번 고른 것은 되돌리지 않는 방법이다. 정렬 한 번과 반복 한 번으로 끝나서 빠르고 코드도 짧다. 문제는 지금 좋아 보이는 선택이 나중에 손해가 되는 경우가 많다는 것이다. 그래서 “이렇게 골라도 손해가 없다”는 이유를 댈 수 있을 때만 믿는다.

예시로 보기

맞는 경우: 회의실 배정

회의실 하나에 회의 8개가 신청되었다. 겹치지 않게 가장 많은 회의를 넣는다. 한 회의가 끝나는 시각에 다음 회의를 바로 시작해도 된다.

회의	A	B	C	D	E	F	G	H
시작 ~ 끝	1 ~ 4	3 ~ 5	0 ~ 6	5 ~ 7	3 ~ 8	5 ~ 9	6 ~ 10	8 ~ 11

가장 먼저 끝나는 회의부터 본다. 앞서 넣은 회의와 겹치지 않으면 넣는다.

A(4에 끝남)를 넣는다. 이제 4 이후에 시작하는 회의만 된다.
B(3 시작), C(0 시작)는 겹친다. D(5 ~ 7)를 넣는다.
E, F, G는 7 전에 시작해서 겹친다. H(8 ~ 11)를 넣는다.

A, D, H로 3개다. 모든 조합을 다 봐도 3개가 최대다.

그림의 회의는 위에서부터 끝나는 시각 순이고, 파란 막대가 고른 A, D, H다. 점선은 앞서 고른 회의가 끝나는 시각이다. 그 점선보다 먼저 시작하는 회색 막대는 모두 건너뛴다¹.

def max_meetings(meetings):
    count, end = 0, float("-inf")
    for s, e in sorted(meetings, key=lambda m: m[1]):   # 끝나는 시각 순
        if s >= end:            # 앞 회의가 끝난 뒤에 시작하면 넣는다
            count += 1
            end = e
    return count

틀리는 경우: 기준을 잘못 고르면

“가장 먼저 시작하는 회의부터”는 그럴듯하지만 틀린다. 회의가 (0 ~ 10), (1 ~ 2), (3 ~ 4)면 0 ~ 10을 먼저 넣어 1개로 끝난다. 실제로는 (1 ~ 2), (3 ~ 4) 두 개를 넣을 수 있다.

동전도 마찬가지다. 1원, 3원, 4원 동전으로 6원을 가장 적은 개수로 내려고 큰 동전부터 쓰면 4 + 1 + 1로 3개다. 3 + 3이면 2개다².

맞는 이유를 보이는 법: 바꿔치기

그리디가 맞다는 것은 흔히 바꿔치기(교환 논증)로 보인다. “가장 좋은 답이 무엇이든, 그 답의 첫 선택을 그리디의 선택으로 바꿔도 손해가 없다”를 보이는 것이다.

회의실 배정에 써 본다. 가장 먼저 끝나는 회의를 g라 하자. 가장 많은 회의를 넣은 어떤 답 O가 있고, O에서 가장 먼저 끝나는 회의를 o라 하자.

g는 모든 회의 중 가장 먼저 끝나니, o보다 늦게 끝나지 않는다.
O에서 o 다음 회의들은 모두 o가 끝난 뒤에 시작한다. 그러니 g가 끝난 뒤에도 시작한다.
그래서 O에서 o를 g로 바꿔도 겹치지 않고, 회의 수는 그대로다.

즉 g를 넣는 가장 좋은 답이 반드시 있다. g를 넣은 뒤 남는 문제(“g가 끝난 뒤 시작하는 회의들에서 가장 많이 넣기”)도 같은 모양이라, 같은 논리를 되풀이하면(수학적 귀납법) 그리디 전체가 가장 좋은 답을 낸다³.

검증: 예시의 회의 8개에서 그리디가 A, D, H를 고르고 최대가 3임, 무작위 회의 묶음 1,500개에서 끝나는 시각 순 그리디가 모든 조합을 보는 방법과 같은 개수를 내는 것, “먼저 시작”, “짧은 것”, “겹침이 적은 것” 기준이 틀리는 예, 1·3·4원 동전의 반례, 10·50·100·500원 동전은 1만 원까지 그리디가 늘 최소 개수를 내는 것을 확인했다 — 22_greedy_verify.py

활용

비용: 대개 정렬 \(O(n \log n)\) + 한 번 훑기 \(O(n)\)이다.
알아보는 신호: 정렬하면 “가장 ~한 것부터 처리”라는 자연스러운 순서가 보인다. 작은 예를 손으로 풀었을 때 되돌아갈 일이 없다.
쓰기 전 점검: 기준을 정했으면 반례를 찾아본다. 작은 입력에서 완전탐색과 무작위로 비교하는 것이 가장 확실하다. 다만 무작위 비교도 반례를 놓칠 수 있다. 무작위로 만든 입력 가운데 반례의 비율이 \(p\)이고 입력을 서로 독립으로 만들면, \(N\)번 안에 반례를 하나도 못 만날 확률은 \((1 - p)^N\)이다. \(p = 0.001\)이면 1,500번 비교해도 반례를 못 만날 확률이 약 22%다(기하분포의 꼬리 확률). 반례가 나오면 동적 계획법을 생각한다.
판정 함수로 쓰기: 매개변수 탐색의 “x면 되나?”는 흔히 “앞에서부터 욕심껏 채우기”로 판정한다.
사전 순으로 가장 앞선 답: 앞자리부터 가장 작은 글자를 고르되, 그 글자를 골라도 끝까지 답을 만들 수 있는지 확인한다. 사전 순은 앞 글자부터 정해지니 앞에서 고른 것을 되돌릴 필요가 없다. 미로 탈출 명령어가 이 모양이다.
실제 쓰임: 거스름돈 계산, 허프만 부호화³, 최소 신장 트리(크루스칼·프림), 다익스트라 최단 경로가 모두 그리디다. 뒤의 셋은 최소 신장 트리와 다익스트라에서 다룬다. 허프만 부호화는 확률이 가장 작은 두 묶음을 하나로 합치는 일을 하나가 남을 때까지 되풀이한다. 이렇게 만든 부호는 접두어 부호(어떤 부호도 다른 부호의 앞부분이 아닌 부호) 가운데 평균 길이가 가장 짧다³. 그 평균 길이는 엔트로피 이상, 엔트로피 + 1비트 미만이다(엔트로피).

연결

선수: 정렬과 정렬 기준
맞는지 확인할 때는 완전탐색과 비교한다. 그리디가 틀리는 문제는 흔히 동적 계획법으로 푼다.
맞다는 근거: 수학적 귀납법
그리디 기준이 틀렸다는 것은 반례 하나로 보이지만, 맞다는 것은 맞는 예를 아무리 모아도 보이지 않는다. 추론 규칙과 증명 방법은 이 차이를 \(n = 0\)부터 39까지 모두 소수인데 \(n = 40\)에서 깨지는 \(n^2 + n + 41\)로 보여 준다.
연습: 미로 탈출 명령어, 1,2,3 떨어트리기

자주 하는 오해

“예시 몇 개에서 맞으면 그리디가 맞다”

틀렸다. 그리디는 기준이 조금만 달라도 맞다가 틀린다. 회의실 배정에서 “먼저 시작하는 것”, “짧은 것”, “다른 회의와 덜 겹치는 것”은 모두 그럴듯하고 작은 예에서는 맞기도 하지만, 셋 다 틀리는 입력이 있다. “먼저 끝나는 것”만 늘 맞는다. 예시에서 맞는 것은 틀리는 입력을 아직 못 만난 것일 뿐이다. 확인하려면 바꿔치기로 증명하거나, 작은 입력 수천 개에서 완전탐색과 비교해 본다.

과목별 관점

자료구조 (1-2학기). 강의에는 가장 좋은 답을 보장하지 못하는데도 쓰는 그리디가 나온다. 똑같은 기계 \(m\)대에 작업 \(n\)개를 나눠 맡겨 마지막 작업이 끝나는 시각을 가장 이르게 하는 문제다. 오래 걸리는 작업부터, 그때 가장 먼저 비는 기계에 맡긴다(LPT). 기계 3대에 걸리는 시간이 6, 2, 3, 5, 10, 7, 14인 작업을 이렇게 맡기면 16에 끝나고, 이것은 가장 좋은 답이다. 하지만 늘 그렇지는 않다. 기계 2대에 3, 3, 2, 2, 2를 맡기면 LPT는 7에 끝나는데 가장 좋은 일정은 6에 끝난다⁴.

요약의 “손해가 없다는 이유를 댈 수 있을 때만 믿는다”와 어긋나 보이지만 사정이 다르다. 이 문제는 가장 좋은 답을 빨리 찾는 방법이 알려져 있지 않다(NP-hard). 그래서 “정답인가” 대신 “정답에서 얼마나 벗어날 수 있는가”를 따진다. LPT의 답은 가장 좋은 답의 \(\frac43 - \frac{1}{3m}\)배를 넘지 않는다. 바꿔치기로 “손해가 없다”를 보이는 대신 “손해가 이만큼을 넘지 않는다”를 보인 것이다. 가장 먼저 비는 기계는 최소 힙으로 찾는다: LPT 스케줄링.

확인 문제

C1 동전이 1원, 3원, 4원일 때 “큰 동전부터 최대한 쓰기”가 가장 적은 개수를 내지 못하는 금액과, 그때 그리디와 실제 최소 개수는?

답: 6원. 그리디는 4 + 1 + 1로 3개, 실제 최소는 3 + 3으로 2개다. 4원을 쓰는 순간 남은 2원을 1원 두 개로 내야 해서 손해가 난다. 우리나라 동전(10, 50, 100, 500원)은 큰 동전이 작은 동전의 배수라 이런 일이 없다.

C2 회의실 배정에서 “가장 먼저 끝나는 회의를 넣어도 손해가 없는” 까닭을 설명하라.

답: 가장 좋은 답의 첫 회의 o를 가장 먼저 끝나는 회의 g로 바꿔 보면 된다. g는 o보다 늦게 끝나지 않으니, o 뒤의 회의들은 g와도 겹치지 않는다. 바꿔도 회의 수는 그대로라, g를 넣는 가장 좋은 답이 있다.

C3 “가장 짧은 회의부터 넣기”가 틀리는 회의 세 개를 만들어라.

답: (0 ~ 5), (4 ~ 6), (5 ~ 10). 가장 짧은 4 ~ 6을 먼저 넣으면 나머지 둘과 모두 겹쳐 1개다. 실제로는 (0 ~ 5), (5 ~ 10) 두 개를 넣을 수 있다. 짧은 회의가 긴 회의 두 개의 경계에 걸쳐 있으면 둘 다 막는다.

22_greedy_plot.py로 그렸고, 그리디가 A, D, H를 고른다는 것과 모든 조합을 봐도 최대가 3이라는 것을 같은 코드로 확인했다. ↩
Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 6.1 “Coin problem”: 동전 {1, 3, 4}로 6을 만들 때 그리디는 4 + 1 + 1, 최적은 3 + 3이다. ↩
같은 책 6.2 “Scheduling”(가장 먼저 끝나는 일부터 고르면 최적), Cormen 외, Introduction to Algorithms 3판, 16.1절 “An activity-selection problem”(같은 문제의 증명), 16.3절 “Huffman codes”(허프만 부호화도 그리디이고, 만든 부호는 최적 접두어 부호다). ↩ ↩² ↩³
수치는 모든 맡기는 방법을 다 해 보는 코드와 견줘 확인했다: 29_lpt-scheduling_verify.py. ↩