greedy, 즉 그리디 알고리즘은 지금 순간에 가장 좋아 보이는 선택을 반복해 답을 만드는 방식입니다. 설명만 들으면 쉬워 보이지만, 실제 코딩테스트에서는 선택 기준을 잘못 잡아 틀리는 경우가 많습니다.
그래서 그리디에서 가장 중요한 습관은 내가 고른 기준이 전체 최적을 보장하는지 반례로 먼저 의심하는 것입니다. 정렬 한 번으로 풀리는 문제가 아니라, 왜 그 정렬이 맞는지 설명할 수 있어야 합니다.
greedy 알고리즘은 선택 기준이 전부다
그리디 문제를 보면 보통 정렬이 먼저 떠오릅니다. 하지만 무엇을 기준으로 정렬할지가 핵심입니다. 값이 큰 순서인지, 무게가 작은 순서인지, 끝나는 시간이 빠른 순서인지에 따라 답이 완전히 달라집니다.
그리디가 통하려면 지금의 선택을 고정해도 나중에 더 좋은 전체 답을 놓치지 않아야 합니다. 이 성질이 없으면 첫 선택은 좋아 보여도 뒤에서 막힙니다.
회의실 배정 예시
대표 예시는 회의실 배정입니다. 겹치지 않는 회의를 최대한 많이 고르고 싶을 때, 시작 시간이 빠른 순서나 길이가 짧은 순서가 먼저 떠오를 수 있습니다. 하지만 표준적인 선택 기준은 끝나는 시간이 빠른 회의를 먼저 고르는 것입니다.
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
meetings.sort(key=lambda x: x[1]) # 끝나는 시간 기준
count = 0
last_end = 0
for start, end in meetings:
if start >= last_end:
count += 1
last_end = end끝나는 시간이 빠른 회의를 고르면 뒤에 남는 시간이 가장 넓어집니다. 이 기준은 다음 선택지를 최대한 많이 열어두는 방향입니다.
반례는 틀린 기준을 드러낸다
시작 시간이 빠른 회의를 먼저 고르는 기준을 생각해 봅시다. 가장 빨리 시작하는 회의가 너무 길면, 뒤의 짧은 회의 여러 개를 모두 놓칠 수 있습니다.
A: 0 ~ 10
B: 1 ~ 2
C: 2 ~ 3
D: 3 ~ 4
시작 시간이 빠른 순서: A 하나 선택
끝나는 시간이 빠른 순서: B, C, D 선택이 작은 예시 하나만으로 시작 시간 기준은 틀렸다는 것을 알 수 있습니다. 좋은 반례는 큰 입력보다 더 강합니다. 왜냐하면 선택 기준의 약점을 바로 보여주기 때문입니다.
그리디 후보 기준을 검증하는 순서
- 먼저 자연스러운 선택 기준을 적는다
- 그 기준이 실패할 수 있는 작은 입력을 만든다
- 다른 선택 기준과 결과를 비교한다
- 선택을 바꿔도 최적해가 유지된다는 설명을 붙인다
- 코드로 옮기기 전에 정렬 기준과 동률 처리까지 정한다
교환 논증을 가볍게 이해하기
교환 논증은 내가 고른 greedy 선택을 최적해 안에 넣어도 손해가 없다는 식으로 설명하는 방법입니다. 이름은 어렵지만 감각은 단순합니다.
회의실 배정에서는 최적해가 어떤 첫 회의를 골랐더라도, 그 첫 회의를 더 빨리 끝나는 회의로 바꿔도 뒤의 회의를 더 방해하지 않습니다. 그래서 끝나는 시간이 빠른 회의를 먼저 골라도 최적해를 잃지 않는다고 볼 수 있습니다.
자주 틀리는 패턴
- 값이 큰 것부터 고르면 항상 좋다고 생각한다
- 정렬 기준은 맞지만 동률 처리를 빼먹는다
- 음수, 0, 같은 값처럼 경계 입력을 확인하지 않는다
- 지역 최적 선택이 나중 선택지를 얼마나 줄이는지 보지 않는다
- DP나 완전탐색이 필요한 문제를 그리디로 단정한다
핵심 기준
greedy 문제에서 코드는 보통 짧습니다. 어려운 부분은 코드가 아니라 어떤 선택 기준이 전체 최적을 보장하는지 확인하는 일입니다.
그래서 반례부터 봐야 합니다. 반례를 만들 수 있으면 그 기준은 틀린 기준입니다. 반례가 잘 안 나오고 선택을 바꿔도 손해가 없다는 설명이 붙으면 그때 구현으로 넘어갑니다.
나쁜 기준은 그럴듯해 보인다
회의실 배정 문제에서 시작 시간이 빠른 회의부터 고르는 기준은 자연스럽습니다. 하지만 긴 회의 하나가 뒤의 짧은 회의 여러 개를 막으면 바로 틀립니다.
회의 목록:
A: 0 ~ 10
B: 1 ~ 2
C: 2 ~ 3
D: 3 ~ 4
시작 시간 기준:
A 선택 -> 1개
끝나는 시간 기준:
B, C, D 선택 -> 3개동률 처리는 작지만 중요하다
정렬 기준이 맞아도 동률 처리가 빠지면 구현이 흔들릴 수 있습니다. 끝나는 시간이 같을 때 시작 시간이 빠른 것을 먼저 볼지, 늦은 것을 먼저 볼지에 따라 중간 과정은 달라집니다.
항상 답이 달라지는 것은 아니지만, 동률 기준을 명시하면 디버깅과 설명이 쉬워집니다.
meetings.sort(key=lambda meeting: (meeting.end, meeting.start))그리디가 맞는지 보는 4단계
- 가장 자연스러운 선택 기준을 하나 적는다
- 그 기준이 실패할 작은 입력을 만든다
- 실패하면 기준을 바꾼다
- 실패하지 않으면 왜 손해가 없는지 말로 설명한다
교환 논증을 말로 풀기
교환 논증은 어렵게 들리지만, 핵심은 ‘최적해의 일부를 내가 고른 선택으로 바꿔도 더 나빠지지 않는다’입니다.
회의실 배정에서는 최적해가 첫 회의로 어떤 회의를 골랐더라도, 그것보다 더 빨리 끝나는 회의로 바꾸면 뒤에 남는 시간이 줄어들지 않습니다. 그래서 끝나는 시간이 빠른 회의를 먼저 골라도 손해가 없다고 볼 수 있습니다.
DP와 헷갈리는 순간
지금 좋은 선택이 나중 선택에 복잡하게 영향을 주면 greedy보다 DP가 필요할 수 있습니다. 특히 선택을 되돌려야 하거나, 여러 상태를 기억해야 최적해가 보이는 문제는 의심해야 합니다.
- 현재 선택이 미래 선택지를 단순히 줄이는 정도가 아니다
- 같은 부분 문제가 여러 번 반복된다
- 최댓값, 최솟값을 상태별로 비교해야 한다
- 작은 반례가 계속 나온다
연습할 때의 루틴
- 문제에서 ‘가장 먼저’, ‘최대한 많이’, ‘최소 비용’ 표현을 찾는다
- 정렬 후보를 2~3개 적는다
- 각 후보마다 작은 반례를 만든다
- 남은 후보에 대해 손해가 없다는 설명을 붙인다
- 그다음 코드를 작성한다
동전 문제는 좋은 반례 연습이다
동전 거스름돈 문제는 greedy가 되는 경우와 안 되는 경우를 같이 보여줍니다. 1, 5, 10, 50처럼 익숙한 동전 체계에서는 큰 동전부터 고르는 방식이 잘 맞아 보입니다.
하지만 동전이 1, 3, 4이고 금액이 6이라면 큰 동전부터 고르는 기준은 4+1+1로 3개를 고릅니다. 최적은 3+3으로 2개입니다.
coins = [1, 3, 4]
amount = 6
greedy:
4 + 1 + 1 = 3 coins
optimal:
3 + 3 = 2 coins이 반례가 알려주는 것
큰 값을 먼저 고르는 기준은 직관적이지만 항상 맞지는 않습니다. 선택 하나가 뒤의 선택지를 어떻게 바꾸는지 봐야 합니다.
- 큰 값 하나가 남은 금액을 애매하게 만들 수 있다
- 작은 값 여러 개가 더 좋은 조합을 만들 수 있다
- 반례가 나오면 greedy가 아니라 DP를 검토해야 한다
- 문제의 동전 체계가 특수한 조건을 갖는지 확인해야 한다
그리디 문제에서 많이 쓰는 정렬 기준
그리디 문제는 정렬 기준이 핵심입니다. 자주 나오는 기준을 외우는 것보다, 각 기준이 어떤 선택지를 남기는지 이해해야 합니다.
- 끝나는 시간이 빠른 순서: 뒤에 남는 시간을 넓힌다
- 마감 시간이 빠른 순서: 늦게 처리할 위험을 줄인다
- 비용이 작은 순서: 제한된 예산에서 후보를 많이 남긴다
- 이익이 큰 순서: 단순하지만 반례가 자주 필요하다
- 비율이 큰 순서: fractional 문제와 0/1 문제를 구분해야 한다
분수 배낭과 0/1 배낭을 구분한다
가치/무게 비율이 큰 물건부터 담는 전략은 분수 배낭에서는 자연스럽습니다. 물건을 쪼갤 수 있기 때문입니다. 하지만 0/1 배낭에서는 물건을 쪼갤 수 없으므로 같은 전략이 틀릴 수 있습니다.
fractional knapsack:
물건을 일부만 담을 수 있음
-> 가치/무게 비율 greedy 가능
0/1 knapsack:
물건을 통째로 담거나 안 담아야 함
-> DP가 필요할 수 있음구현 전에 적어볼 문장
그리디 풀이를 제출하기 전에는 한 문장으로 기준을 설명해 보는 것이 좋습니다. 설명이 안 되면 코드가 맞을 확률도 낮습니다.
- 나는 무엇을 먼저 고르는가?
- 그 선택이 뒤 선택지를 더 나쁘게 만들지 않는 이유는 무엇인가?
- 동률일 때 어떤 기준을 쓰는가?
- 작은 반례를 3개 이상 통과했는가?
- DP로 풀어야 하는 신호는 없는가?
정리
그리디 알고리즘은 코드를 짧게 만드는 기술이 아니라, 맞는 선택 기준을 찾는 사고법입니다. 선택 기준이 맞으면 구현은 단순해지고, 기준이 틀리면 아무리 깔끔한 코드도 틀립니다.
관련해서 내부 글은 DP에서 메모이제이션과 테이블 방식은 무엇이 다를까, 투 포인터 알고리즘이란 무엇인가, 우선순위 큐는 언제 써야 할까와 함께 보면 좋습니다.
외부 기준은 CP-Algorithms – Scheduling jobs on one machine, MIT OCW – Introduction to Algorithms, Python Docs – Sorting HOW TO를 기준으로 확인했습니다.
