그리디 알고리즘의 최적화의 경우를 알고리즘 예시를 들어 설명하고, 그러디 알고리즘이 최적화 적용 알고리즘으로 선택이 안되는 경우도 예시를 들어 이유를 설명하시오
분야
hwp대표적인 그리디 알고리즘의 예시로는 동전 거스름돈 문제가 있다. 이 문제에서 주어진 금액을 거슬러주기 위해 가장 적은 수의 동전을 사용하는 방법을 찾는 것이다. 예를 들어, 1원, 5원, 10원, 50원, 100원, 500원의 동전이 있을 때, 760원을 거슬러주어야 한다면 그리디 알고리즘은 가장 큰 동전부터 차례로 선택하여 거슬러주는 방식을 사용한다. 즉, 500원 동전을 먼저 선택하고, 남은 금액인 260원을 다시 거슬러준다. 다음으로 100원 동전 두 개를 선택하여 60원이 남고, 그 후 50원 동전 하나, 10원 동전 하나를 선택하여 정확히 760원을 거슬러주게 된다. 이 방법을 통해 총 6개의 동전으로 문제를 해결할 수 있다. 이 경우 그리디 알고리즘은 최적의 해를 제공한다.