[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 파트에서 다룰 예정)

 

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

 

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

 

 

참고) 동전 거스름돈 문제에서 그리디 방식 증명

10원, 100원, 50원, 500원 화폐가 있을 때, 500원 화폐를 최대한 많이 사용하면 동전의 개수를 최대한 줄일 수 있을 것 같지만, 이를 아직 수학적으로는 증명해보진 않았기 때문에, 직접 증명해보겠다.

 

보조 정리 1) 동전을 최소로 소모하면서 물건 값을 지불하려면 10/100원 동전은 4개 이하, 50원 동전은 1개 이하로 사용해야 한다.

 

이를 귀류법을 이용해서 증명해보자

 

정리1- 증명) 10/100원 동전을 5개 이상 사용하면 50/500원 동전으로 대체 가능하고, 50원 동전을 2개 이상 사용하면 100원 동전으로 대체 가능하기 때문에 최소 개수가 되지 않는다 --> 정리1 증명

 

명제) 동전을 최소로 소모하면서 지불하려면 500원 동전을 최대한 많이 써야 한다. 

 

증명) 10, 50, 100원 동전으로는 물건 값을 최대 10X4 + 50 X 1 + 100 X 4 = 490원만 감당 가능하다. 500원을 다 사용하지 않을 경우 10, 50, 100원 동전으로 500원 이상을 감당해야 하기 때문에 보조 정리처럼 귀류법으로 증명할 수 있다.

 

위 그리디 방식은 동전 간의 배수 관계가 성립할 때 사용할 수 있음에 주의하자.

 

 

Ref) 알기쉬운 알고리즘

Ref) 바둑킹 실전 알고리즘