[C 언어] 탐욕 알고리즘 (Greedy algorithm)

Coin change problem

탐욕 알고리즘은 눈 앞에 놓인 선택지 중에 현재 상황에서 가장 최선의 것을 선택하도록 디자인 된 알고리즘이다.

알고리즘은 일상에서 coin change problem, 즉 상점에서 잔돈 돌려주는 상황에 써먹을 수 있는데,

돌려줘야 될 잔돈의 수에 따라서 quarters 25, dimes 10, nickels 5, pennies 1 중 최선을 선택해야 한다.

여기서 최선의 선택이란 가장 높은 가치의 돈 (만약 >=25 이라면 25)을 우선으로 선택하고 남는 돈은 그 다음 (10->5->1)로 넘어가는 것이다.

이렇게 잔돈을 돌려주도록 코딩을 하기 위해서는 알고리즘처럼 직관적으로 생각하면 된다.  25 부터 1까지 순서대로 정렬한 후, 반복문을 돌면서 조건이 끝나는 때 남는 돈이 다음 반복문에 나오는 돈보다 많을 경우 추가해서 계산을 하면 된다.

 

datatype int 로 argument 를 설정한다.