언제 쓰나
- “최대한 많이”, “최소 개수로”, “가장 빨리” — 최적화 문제인데 DP를 쓰기엔 상태가 단순할 때
- 회의실 배정, 동전 거스름돈, 작업 스케줄링처럼 한 번의 선택이 이후 선택을 제한하지 않는 구조
N이 커서(10만+) 완전 탐색·DP가 불가능한데, “정렬하고 앞에서부터 고르면 될 것 같은” 직감이 드는 문제
핵심 아이디어
미래를 보지 않고 지금 가장 좋은 것을 고른다. 대신 “지금 최선이 전체 최선”이라는 근거가 있어야 한다 — 대부분은 정렬 기준이 그 근거다.
회의실 배정: 겹치지 않게 최대한 많은 회의를
회의를 '끝나는 시간' 순으로 정렬:
[1───3]
[2────5] ✗ 3보다 먼저 시작 → 버림
[4──6] ✓ 채택 (끝 6)
[5───8] ✗
[7─9] ✓ 채택
왜 끝나는 시간순인가: 빨리 끝나는 회의를 고를수록
남는 시간이 최대 → 이후 선택지가 가장 넓다“시작 시간순”이나 “짧은 순”으로 정렬하면 반례가 존재한다. 그리디에서 정렬 기준을 고르는 일이 곧 증명이다.
코드 템플릿
그리디는 알고리즘보다 패턴이다 — 정렬 후 순회하며 조건 검사.
def max_meetings(meetings): # [(start, end), ...]
meetings.sort(key=lambda m: (m[1], m[0])) # 끝나는 시간순
count, last_end = 0, 0
for start, end in meetings:
if start >= last_end: # 이전 회의와 안 겹치면 채택
count += 1
last_end = end
return count동전 거스름돈 — 큰 단위부터 최대한.
def min_coins(coins, amount): # coins는 내림차순
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count단, 이 풀이는 한국 동전처럼 큰 단위가 작은 단위의 배수일 때만 최적이다. [1, 3, 4]로 6을 만들면 그리디는 4+1+1(3개)이지만 답은 3+3(2개) — 이런 단위 체계면 DP로 가야 한다.
풀이 과정 따라가기
회의 5개를 끝나는 시간순으로 정렬한 뒤 채택/버림을 결정하는 과정이다.
함정
- 그리디가 성립하는지 먼저 의심한다. “일단 정렬하고 골랐더니 예제가 맞았다”는 증명이 아니다. 작은 반례를 2~3개 직접 만들어보고, 안 만들어지면 믿는다.
- 정렬 기준의 타이브레이크. 회의실 문제에서 끝 시간이 같으면 시작 시간 순으로도 정렬해야 (0,0) 같은 순간 회의가 누락되지 않는다.
- 그리디 vs DP 갈림길. 선택이 미래의 선택지를 바꾸면(동전
[1,3,4]) 그리디가 깨진다. 반례가 하나라도 나오면 미련 없이 DP로 전환한다..