그리디 알고리즘

동전교환문제

동전교환문제

• • 서로 다른 단위의 동전이 주어졌을 때, 거스름돈을 동전의 개수가 최소가 되도록 교환해 주려고 한다. 이때 교환해 주는 동전의 최소 개수와 교환해 주는 동전의 조합을 계산하시오. 단, 모든 단위의 동전은 무수히 많다고 가정한다. -ex:
    • 동전의 종류 : 1원, 5원, 10원, 21원 ,25원
    • 거스름 돈 : 63원
      • 최소동전개수 : 3개
      • {21,21,21}

다음과 같은 문제는 최적화 문제이며 다이나믹 프로그래밍으로 해결이 가능하다. 다이나믹 프로그래밍으로 문제를 풀 때는 총 4가지 스텝이 존재한다.

1. 문제분석 → Working Backwark (처음부터가 아닌 뒤부터 생각한다.)

2. Recursive 가장 중요하며 반복이 많다.

3. Bottorm up 방식 → 쟉은 data부터 큰 data로 계산값들을 Table에 저장한다.

4. 3번과정에서 나오는 추가적인 정보를 Table에 저장

단계 1: 동전조합의 구조분석

• 동전의 종류 : n가지 → 1원, 5원, 10원, 21원, 25원
• 거스름 돈 : K원 → 63원

단계 2: 재귀식

• C(k) : k원을 바꿀 때, 최소 동전의 개수
• C(63)을 바꾸는 방법은 다섯가지 (동전의 종류가 다섯개이기 때문)
  1. C(38) + 25
  2. C(53) + 10
  3. C(62) + 1
  4. C(42)+ 21
  5. C(58) + 5

  위 식을 정리해보자 어차피 마지막에 동전의 크기와 상관없이 동전이 하나가 추가가 되므로 C(63) = min {C(38), C(42), C(53), C(58), C(62)} + 1(추가 된 동전) 으로 정리가 가능하다.

• 알고리즘
• 그리디