그리디
매 단계에서 지금 보기에 가장 좋은 선택을 하고, 그 선택을 다시 번복하지 않는 알고리즘 설계 기법입니다.
동작 과정
거스름돈 문제로 그리디의 선택 과정을 추적합니다.
동전 단위 = [500, 100, 50, 10] 거슬러줄 금액 = 860
860원, 가장 큰 단위 500부터 시도
500 ≤ 860 → 500 사용, 남은 금액 360, 개수 1
500 > 360 → 다음 단위로
360원, 100 시도
100 ≤ 360 → 100 사용, 남은 금액 260, 개수 2
100 ≤ 260 → 100 사용, 남은 금액 160, 개수 3
100 ≤ 160 → 100 사용, 남은 금액 60, 개수 4
100 > 60 → 다음 단위로
60원, 50 시도
50 ≤ 60 → 50 사용, 남은 금액 10, 개수 5
50 > 10 → 다음 단위로
10원, 10 시도
10 ≤ 10 → 10 사용, 남은 금액 0, 개수 6
남은 금액 0 → 종료, 총 동전 개수 6
매 단계에서 "지금 쓸 수 있는 가장 큰 단위"를 선택하고, 그 선택을 되돌아보지 않습니다. 이후 단계에서 이전 선택을 다시 고려하지 않는다는 점이 그리디의 핵심입니다.
구현
int greedyChange(int[] coins, int amount) { // coins는 내림차순 정렬되어 있다고 가정
int count = 0;
for (int coin : coins) {
count += amount / coin;
amount %= coin;
}
return amount == 0 ? count : -1; // 남은 금액이 있으면 이 동전 체계로는 불가능
}
복잡도
| 구현 방식 | 시간 | 근거 |
|---|---|---|
| 동전 단위가 이미 정렬됨 | O(단위 개수) | 단위마다 나눗셈·나머지 연산 한 번씩 |
| 동전 단위를 직접 정렬 | O(k log k) | k개 단위를 정렬하는 비용이 지배적 |
공간복잡도는 O(1)로, 추가 자료구조 없이 누적 변수만 사용합니다.
주의사항
- 그리디는 항상 최적해를 보장하지 않는다. 동전 단위가
[1, 3, 4]이고 목표가 6원이면, 그리디는4 + 1 + 1(3개)을 고르지만 실제 최적해는3 + 3(2개)이다. 단위 사이의 배수 관계가 깨지면 그리디가 틀릴 수 있다 - 그리디가 최적해를 보장하려면 탐욕적 선택 속성(매 단계의 지역 최적 선택이 전체 최적해에 포함됨)과 최적 부분 구조를 모두 만족해야 한다. 이 증명이 안 되면 동적 계획법처럼 모든 경우를 고려하는 방법을 써야 한다
- 그리디는 선택을 번복하지 않는다. 백트래킹처럼 되돌아가지 않으므로 한 번 내린 선택이 틀렸다고 판단되는 순간이 와도 수정할 수 없다