[Algorithm/Greedy] 동전 거스름돈 문제

동전 거스름돈(Coin Change) 문제란?

• 동전 거스름돈의 최소 동전 수를 찾는 그리디 알고리즘
  • 달성 목표 : 최소 동전 수
  • 제한 조건 : 거스름돈의 가치가 같도록 한다

 

그리디 방식의 동전 거스름돈을 결정하는 해결 문제

• 매 순간마다 남은 거스름돈의 총액을 초과하지 않는 조건하에 ‘greedy, 욕심내어’ 가장 큰 액면의 동전을 취함
• 가장 큰 액면을 가진 동전부터 차례로 선택하여 남은 거스름돈 액수보다 작을 경우 해답에 포함시킨다

슈도 코드

동전의 액면은 500원, 100원, 50원, 10원, 1원이라고 할 때

입력 : 거스름돈 액수 W

출력 : 거스름돈 액수에 대한 최소 동전수

1. change=W, n500=n100=n50=n10=n1=0
	// n500, n100, n50, n10, n1은 각각의 동전 카운트
2. while ( change ≥ 500 ) // 근시안 적인 선택 !!
	change = change-500, n500++ // 500원짜리 동전 수를 1 증가
3. while ( change ≥ 100 )
	change = change-100, n100++ // 100원짜리 동전 수를 1 증가
4. while ( change ≥ 50 )
	change = change-50, n50++ // 50원짜리 동전 수를 1 증가
5. while ( change ≥ 10 )
	change = change-10, n10++ // 10원짜리 동전 수를 1 증가
6. while ( change ≥ 1 )
	change = change-1, n1++ // 1원짜리 동전 수를 1 증가
7. return (n500+n100+n50+n10+n1) // 총 동전 수를 리턴한다.

 

• 앞의 알고리즘은 남아있는 거스름 돈인 change에 대해 가장 높은 액면의 동전을 거스른다.
• 그리디 알고리즘의 근시안적인 특성 : 500원짜리 동전을 처리하는 과정에서 100원짜리, 50원짜리, 10원짜리, 1원짜리 동전을 몇 개 씩 거슬러 주어야 할 것인지에 대해서는 전혀 고려하지 않는다.

 

그리디 방식의 CoinChange 알고리즘은 항상 최적의 답을 주는 것일까?

 만약 동전 거스름돈 문제에서, 160원짜리 새로운 동전의 종류가 추가된다면, CoinChange 알고리즘이 항상 최소 동전 수를 계산할 수 있을까?

• 거스름돈이 200원이라면, CoinChange 알고리즘은 160원짜리 동전 1개와 10원짜리 동전 4개로서 총 5개를 리턴한다.
  • 최적해는 100원 X 2 이다.

따라서 그리디 방식의 CoinChange 알고리즘은 항상 최적의 답을 주는 것은 아니다. (DP 알고리즘으로 최적의 답을 구할 수 있는데, DP 파트에서 다룰 예정)

 

이 그리디 알고리즘으로 거스름돈 교환 문제를 풀게된다면, 큰 단위의 동전이 작은 단위의 동전의 배수가 되어야 그리디 알고리즘을 적용할 수 있음

 

그렇기 때문에, 그리디 알고리즘을 사용할 때에는 전체적인 최적해 인지를 항상 염두할 필요가 있음. 즉, 그리디 알고리즘을 사용하기 전에 그리디 알고리즘을 사용해도 되는지 검증 단계를 거쳐야 함.

 

Ref) 알기쉬운 알고리즘