Coin Change Algorithm(거스름돈 알고리즘)

알고리즘 공부를 시작한게 된 건 컴퓨터적인 사고방식을 키우고자 함이다.


알고리즘을 컴퓨터로 구현하기 위해서는 선행지식과 처리과정을 알고있어야한다.


첫째로 거스름돈 알고리즘을 짜보았다.

거스름돈 알고리즘이란, 우리가 보통 돈을받고 거스름돈을 줄때 가장 큰 단위의 지폐부터

주고 그 다음 큰 단위 그다음 그다음 이런식으로 차례로 화폐를 교환 해주는것을 컴퓨터로

계산하게 만든 알고리즘을 말한다.

예를들어 9700원을 효율적으로 주려면, 5000원 짜리 1장, 1000원짜리 4장, 5원짜리 1개,

100원짜리 2개로 거슬러 주는것이다.

 위와 같이 코인을 입력받으면

이렇게 가장효율적으로 거슬러주는 프로그램이다.


다음은 이 알고리즘을 컴퓨터로 구현하는 과정

1. 선행지식

이 알고리즘을 구현하기 위해 필요한 선행지식으로는 우리는 가장 큰 단위의 화폐부터

작은 단위의 화폐 순으로 계산해 나가야 한다는 선행지식을 알아야한다.



2. 처리과정 [동전(500원, 100원, 50원, 10원) 으로만 바꿔주는 프로그램을 짜봤다]

1) 입력받은돈을 500원으로 나눠 나오는 몫이 500원의 갯수

2) 500원으로 나누고 남은 나머지 에서 100으로 나눠서 나오는 몫이 100 원의 갯수

3) 2)의 과정처럼 100으로 나머지 연산하고 남은 값을 50으로 나오는 몫이 50원의 갯수

4) 3)의 과정과 같이 10원의 갯수를 구한다.

다음은 위의 선행지식과 처리과정을 이용해 코딩을 한것이다.

Calculate 함수를 보면 2.처리과정을 잘 이해할 수있다.