개념
매 단계에서 가장 좋아 보이는 선택을 하여 전체적으로 최적해를 구하는 알고리즘 설계 기법이다.
핵심 특징
- 탐욕적 선택 속성: 현재 최적 선택이 전체 최적해에 포함됨
- 최적 부분 구조: 부분 문제의 최적해로 전체 최적해 구성 가능
- 증명이 중요: 그리디가 최적해를 보장하는지 확인해야 함
DP vs 그리디
| 특성 | DP | 그리디 |
|---|
| 모든 경우 고려 | O | X (최선만 선택) |
| 시간복잡도 | 보통 더 높음 | 보통 더 낮음 |
| 최적해 보장 | 항상 | 조건부 |
| 구현 난이도 | 보통 | 쉬움 (증명이 어려움) |
그리디 정당성 증명
교환 논증 (Exchange Argument)
1
2
3
4
| 1. 최적해 O와 그리디 해 G가 다르다고 가정
2. O에서 G와 다른 부분을 G의 선택으로 교환
3. 교환 후 해가 나빠지지 않음을 증명
4. 따라서 G도 최적해
|
귀류법
1
2
3
| 1. 그리디 해가 최적이 아니라고 가정
2. 모순 도출
3. 따라서 그리디 해가 최적
|
대표 유형
활동 선택 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <bits/stdc++.h>
using namespace std;
// 끝나는 시간 기준으로 정렬 → 겹치지 않는 최대 활동 수
struct Activity {
int start, end;
bool operator<(const Activity& o) const {
return end < o.end;
}
};
int activitySelection(vector<Activity>& acts) {
sort(acts.begin(), acts.end());
int count = 1;
int lastEnd = acts[0].end;
for (int i = 1; i < (int)acts.size(); i++) {
if (acts[i].start >= lastEnd) {
count++;
lastEnd = acts[i].end;
}
}
return count;
}
|
회의실 배정
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<pair<int, int>> meetings(N); // {끝, 시작}
for (int i = 0; i < N; i++) {
cin >> meetings[i].second >> meetings[i].first;
}
// 끝나는 시간 기준 정렬 (같으면 시작 시간)
sort(meetings.begin(), meetings.end());
int count = 0;
int lastEnd = 0;
for (auto [end, start] : meetings) {
if (start >= lastEnd) {
count++;
lastEnd = end;
}
}
cout << count << '\n';
return 0;
}
|
허프만 코딩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <bits/stdc++.h>
using namespace std;
// 빈도가 낮은 것끼리 먼저 합침
long long huffmanCost(vector<int>& freq) {
priority_queue<long long, vector<long long>, greater<>> pq;
for (int f : freq) {
pq.push(f);
}
long long totalCost = 0;
while (pq.size() > 1) {
long long a = pq.top(); pq.pop();
long long b = pq.top(); pq.pop();
totalCost += a + b;
pq.push(a + b);
}
return totalCost;
}
|
사용 예시
동전 거스름돈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
int coins[] = {500, 100, 50, 10};
int count = 0;
for (int coin : coins) {
count += N / coin;
N %= coin;
}
cout << count << '\n';
return 0;
}
|
분할 가능 냅색 (Fractional Knapsack)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
struct Item {
int weight, value;
double ratio() const { return (double)value / weight; }
bool operator<(const Item& o) const {
return ratio() > o.ratio(); // 가치/무게 비율 내림차순
}
};
double fractionalKnapsack(vector<Item>& items, int W) {
sort(items.begin(), items.end());
double totalValue = 0;
int remaining = W;
for (auto& item : items) {
if (remaining >= item.weight) {
totalValue += item.value;
remaining -= item.weight;
} else {
totalValue += item.ratio() * remaining;
break;
}
}
return totalValue;
}
|
최소 회의실 개수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<pair<int, int>> events; // {시간, +1/-1}
for (int i = 0; i < N; i++) {
int s, e;
cin >> s >> e;
events.push_back({s, 1}); // 시작
events.push_back({e, -1}); // 종료
}
sort(events.begin(), events.end());
int cur = 0, maxRooms = 0;
for (auto [t, type] : events) {
cur += type;
maxRooms = max(maxRooms, cur);
}
cout << maxRooms << '\n';
return 0;
}
|
구간 스케줄링 가중치 버전
1
2
3
4
5
| // 가중치가 있으면 그리디가 아닌 DP 필요
// → 그리디가 안 되는 대표적 반례
// 가중치 없음: 그리디 (끝 시간 정렬)
// 가중치 있음: DP + 이분 탐색
|
주의사항 / Edge Cases
그리디가 실패하는 경우
1
2
3
4
5
6
7
8
| // 0-1 냅색: 그리디 (비율 순) 실패
// 예: 용량 10
// 물건 A: 무게 6, 가치 7 (비율 1.17)
// 물건 B: 무게 5, 가치 5 (비율 1.0)
// 물건 C: 무게 5, 가치 5 (비율 1.0)
// 그리디: A 선택 (가치 7)
// 최적: B + C 선택 (가치 10)
|
정렬 기준 실수
1
2
3
4
5
| // 회의실 배정: 끝 시간 정렬 ✅
// 시작 시간 정렬 ❌ (반례 존재)
// 끝 시간이 같으면 시작 시간 기준 추가 정렬
sort(meetings.begin(), meetings.end()); // pair 기본: 첫 번째 → 두 번째
|
오버플로우
1
2
| // 합산 결과가 클 수 있으므로 long long 사용
long long totalCost = 0;
|
면접 포인트
자주 나오는 질문
Q1. 그리디 알고리즘이란?
- 매 단계에서 현재 최적인 선택을 하는 기법
- 탐욕적 선택 속성 + 최적 부분 구조가 만족되어야 함
Q2. 그리디가 최적해를 보장하는지 어떻게 확인하는가?
- 교환 논증: 최적해에서 그리디 선택으로 교환해도 나빠지지 않음
- 귀류법: 그리디 해가 최적이 아니면 모순
- 반례를 찾아봐야 함
Q3. 그리디 vs DP의 선택 기준은?
- 그리디: 증명 가능하면 사용 (더 빠르고 간단)
- DP: 그리디가 안 되면 DP
- 0-1 냅색처럼 그리디가 실패하는 경우 존재
Q4. 대표적인 그리디 알고리즘은?
- 다익스트라, 크루스칼, 프림 (최단경로/MST)
- 활동 선택, 회의실 배정
- 허프만 코딩
- 거스름돈 문제
Q5. 분할 가능 냅색 vs 0-1 냅색?
- 분할 가능: 물건을 쪼갤 수 있음 → 그리디 (비율 순)
- 0-1: 물건을 쪼갤 수 없음 → DP 필요
코드 체크리스트
1
2
3
4
| // 1. 정렬 기준 결정 (핵심!)
// 2. 탐욕적 선택 + 조건 확인
// 3. 정당성 검증 (반례 없는지)
// 4. 오버플로우 / 자료형 확인
|
추천 문제