💡
DP·그리디
회의실·동전·활동 선택
강의 22: 그리디 알고리즘 (Greedy Algorithm)
그리디 풀이의 정당성을 직관·증명으로 확보하는 사고 패턴을 익힙니다.
그리디회의실 배정
소요 시간
⏱ 약 1시간
난이도
📊 중급
선수 조건
🎯 정렬·탐색
결과물
그리디 풀이의 정당성을 직관·증명으로 확보하는 사고 패턴을 익힙니다.
이 강의에서 배우는 것
- 1그리디 알고리즘의 정당성을 교환 논증(exchange argument)으로 증명하는 방법을 이해한다.
- 2활동 선택 문제(회의실 배정)를 종료 시간 기준 정렬로 O(n log n)에 풀 수 있다.
- 3그리디가 실패하는 경우를 인식하고, DP와 그리디의 적용 기준을 구별할 수 있다.
소개
그리디(탐욕) 알고리즘은 **매 단계에서 현재 가장 좋아 보이는 선택**을 해서 전체 최적해를 구하는 방법입니다.
💡
"지금 당장 최선인 선택이 결국 전체 최선이다."
DP와의 차이:
- **DP**: 모든 가능성을 고려, 이전 결과를 저장
- **그리디**: 되돌아가지 않고 현재 최선만 선택
text
그리디가 최적인 조건 (Matroid 이론)
─────────────────────────────────────────────────────
1. 탐욕 선택 속성 (Greedy Choice Property):
지역 최적 선택이 전역 최적해의 일부
2. 최적 부분 구조 (Optimal Substructure):
전체 최적해가 부분 문제의 최적해로 구성
─────────────────────────────────────────────────────
→ 이 두 조건이 성립할 때만 그리디가 최적 보장!핵심 개념
교환 논증 (Exchange Argument)
text
그리디 증명 방법:
1. 최적해가 그리디 해와 다르다고 가정
2. 최적해에서 그리디가 선택한 것과 다른 부분을 교환
3. 교환 후에도 해가 나빠지지 않음을 보임
4. 따라서 그리디 해 ≥ 최적해 → 그리디가 최적활동 선택 (Activity Selection)
text
회의: [(시작, 종료)] 정렬 기준 = 종료 시간!
왜 종료 시간 기준인가?
일찍 끝나는 활동을 선택할수록 다음 활동을 더 많이 선택할 수 있음
예:
활동: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]
정렬: [(1,4), (3,5), (0,6), (5,7), ...]
선택: (1,4) → (5,7) → (8,11) → (12,16) = 4개
시간 복잡도: O(n log n) — 정렬 지배그리디가 실패하는 경우
text
동전 거스름돈 예시:
동전 [1, 5, 6, 9], 금액 11
그리디: 9 + 1 + 1 = 3개
최적: 5 + 6 = 2개 ← 그리디 실패!
∵ 탐욕 선택 속성이 성립하지 않음복잡도 비교
text
┌──────────────────────────┬──────────────┬──────────────┐
│ 문제 │ 그리디 │ DP │
├──────────────────────────┼──────────────┼──────────────┤
│ 활동 선택 │ O(n log n) │ O(n²) │
│ 한국 동전 거스름돈 │ O(k) │ O(n × amount)│
│ Huffman 코딩 │ O(n log n) │ O(n log n) │
│ 최소 회의실 수 │ O(n log n) │ O(n log n) │
└──────────────────────────┴──────────────┴──────────────┘예제로 보기
| 파일 | 내용 |
|---|---|
| `src/01_activity_selection.py` | 회의실 배정 (활동 선택) |
| `src/02_coin_greedy.py` | 동전 거스름돈, 실패 예시 |
| `src/03_meeting_rooms.py` | 최소 회의실 수 (힙) |
| `src/04_greedy_examples.py` | 거스름돈, 최대 곱, 배열 합 |
자주 하는 실수
- **그리디 정당성 증명 생략**: 그리디가 맞을 것 같다고 그냥 적용 — 반드시 교환 논증 또는 반례 탐색 필요
- **정렬 기준 오류**: 활동 선택에서 시작 시간이 아닌 종료 시간으로 정렬해야 함 — 시작 시간 정렬은 틀림
- **동전 문제 그리디 오용**: 동전 배율이 지수적이지 않으면 그리디 실패 — 한국 동전은 1,5,10,50,100,500이라 가능
- **힙 활용 타이밍**: 회의실 수 최소화는 최소 힙(끝나는 시간)을 써야 함 — 우선순위 큐 없이 풀면 O(n²)
- **탐욕 + DP 혼용 오류**: 그리디로 풀리지 않는 문제에 그리디 적용 → 반례 먼저 찾아보기
정리
- 그리디 = **매 단계 최선 선택** + **탐욕 선택 속성** + **최적 부분 구조**
- 정당성은 **교환 논증**으로 증명
- 활동 선택: 종료 시간 정렬 → O(n log n)
- 그리디 실패 시 → DP 또는 백트래킹으로 전환
직접 해 보기
- 허프만(Huffman) 코딩 구현: 빈도 기반 최소 비트 코드 생성
- 최소 신장 트리(크루스칼): 간선 가중치 정렬 후 그리디 선택
- 분수 배낭 문제(Fractional Knapsack): 가치/무게 비율 기준 그리디
과제
📂 `homework/README.md` 참조
- 백준 1931 (회의실 배정) — Silver I
- 백준 11047 (동전 0) — Silver I
- 백준 1744 (수 묶기) — Gold IV