1. 동전교환 문제

많은 사람들이 줄지어 책값을 치르려하고 있다. 한 고객이 책값으로 15,000원을 지폐를 내었다고 하자. 그리고 책값이 13,200원으로 거스름돈 1,800원을 거스름돈으로 내주어야 하는 상황이다. 거스름돈을 어떻게 내주어야 할까? 아마도 대부분의 사람들이 우선 가장 큰 동전인 500원 동전 3개와 100원 동전 3개로 거스름돈을 내줄 것이다. 이것은 너무나도 분명하다. 그렇지 않다면 10원 동전으로 180개를 세어 거스름돈을 내주는 일은 너무도 큰일이 될 것이고 뒤에 기다리는 고객은 화가 날 것이다. 너무도 당연한 일임을 직관적으로 알 수 있다. 그렇다면 어떻게 빠르게 그리고 정확하게 거스름돈을 고객에게 내줄 수 있을까? 그리고 거스름돈의 동전의 개수는 최소가 될까?

2. 문제 해결의 방법

기본 알고리즘인 욕심쟁이, 동적계획법, 분기한정, 분할정복 기법을 이용하여 동전교환 문제를 해결하는 접근 방법을 상세하게 기술하시오. 단, 한 가지만으로 문제를 해결하지 말고 언급된 4개의 방법을 모두 기술하며 어떤 방법의 접근은 문제해결이 가능한지 그리고 가능하다면 어떻게 해결할 수 있는지를 기술하시오. 만일 해결이 불가능하다면 왜 그런지를 기술하시오.

예를 들어, 욕심쟁이 기법으로 동전교환 문제를 해결하기 위해서는 동전의 단위가 문제가 된다는 것을 설명하고 동전의 단위에 상관없이 문제를 해결하기 위해서는 동적 계획법을 이용하거나 분기한정 기법을 이용할 수 있음을 기술하시오.

지금까지 배운 알고리즘의 정리이므로 반드시 모든 기법에 대하여 충분히 이해하고 문제해결의 방법을 서술하시오.