[알고리즘] 그리디 알고리즘(탐욕 알고리즘) 동전 거스름돈 지불 문제

1. 문제 정의

거스름돈 지불 문제는 일상생활에서 자주 접하는 문제로, 특정 금액을 지불할 때 사용할 동전의 종류와 개수를 최소화하는 방법을 찾는 것이다. 예를 들어, 상점에서 상품의 가격이 1,000원이었고 소비자가 2,000원짜리 지폐로 결제를 하려 할 때, 상점 주인이 소비자에게 돌려줘야 할 거스름돈은 1,000원이 된다. 이 상황에서 상점 주인은 동전의 종류가 제한적일 때, 가능한 한 적은 개수의 동전을 사용하여 거스름돈을 제공해야 한다. 이 문제는 특히 다양한 동전 단위가 주어질 때 더욱 복잡해진다. 예를 들어, 동전의 종류가 500원, 100원, 50원, 10원, 1원 등으로 구성되어 있다고 가정하면, 1,000원을 거슬러 줄 때 이러한 동전들을 조합하여 최소한의 개수로 이루어진 조합을 찾아야 한다. 이 상황에서 그리디 알고리즘이 유용하게 활용될 수 있다. 그리디 알고리즘에서는 현재 상황에서 가장 최선의 선택을 하면서 최적의 해법으로 나아가는 방식을 취한다. 즉, 가장 큰 단위의 동전부터 사용하여 거스름돈을 차감해 나가는 방식이다. 이 접근법은 문제를 간단하게 만들고, 쉽게 이해할 수 있게 한다. 그러나 모든 경우에 그리디 알고리즘이 최적의 …