4.1 동전 거스름돈 문제
- 동전 거스름돈 문제를 해결하는 가장 간단한 효율적인 방법
- 남은 액수를 초과하지 않는 조건하에 ‘욕심내어' 가장 큰 액면의 동전을 취하는 것
- 동전 거스름돈 문제의 최소 동전 수를 찾는 그리디 알고리즘
- 동전의 액면은 500원, 100원, 50원, 1원
coinChange(N) 입력 = 거스름돈 액수 W 출력 = 거스름돈 액수에 대한 최소 동전 수 1. D = {10, 50, 100, 500 } //거슬러줄 수 있는 거스름돈 단위의 집합 2. S = { } //답이라고 한다면 3. value = N 4. while(value != 0) x = D에서 x < value 인 가장 큰 값 if 조건에 만족하는 항목이 없으면(D에 해당하는 값이 없을 때) return S = S (합집합) {x} value -= x 5. return S
그리디 알고리즘의 근시안적인 특성
CoinChange 알고리즘은 남아있는 거스름돈인 change에 대해 가장 높은 액면의 동전을 거스르며,
500원 동전을 처리하는 line 2에서는 100원, 50원, 10원 1원 동전을 몇 개씩 거슬러 주어야 할 것인지에 대해서는 전혀 고려하지 않는다.
200원을 거스름돈 주어야 할 때 100원짜리 2개를 주는 것이 가장 좋은 방법일 것이다. 하지만 예를 들어 동전이 160원짜리가 있다면 그리디 알고리즘에 의해 160원 1개 10원 4개를 거스름돈으로 줄 것 이다. 이를 통해 그리디 알고리즘은 항상 정답을 찾는 알고리즘이 아니라는 것을 알 수 있다.
'CS > 알고리즘' 카테고리의 다른 글
Chap4-6. 작업스케줄링(Job scheduling) (0) | 2022.04.15 |
---|---|
Chap4-2. 최소 신장 트리 (0) | 2022.04.11 |
Chap 4. 그리디 알고리즘 (0) | 2022.04.11 |
Chap3-4. 최근접 점의 쌍 찾기(Closest Pair) (0) | 2022.04.08 |
Chap3-2 퀵정렬(QuickSort) (0) | 2022.04.05 |