Chap4-1. 동전 찾기 문제

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개를 거스름돈으로 줄 것 이다. 이를 통해 그리디 알고리즘은 항상 정답을 찾는 알고리즘이 아니라는 것을 알 수 있다.