현재 상황에서 당장 좋은것만 고르는 알고리즘 이다.
예제 3-1 거스름돈
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100월, 50원, 10월이 무한히 존재한다고 가정할 때, 손님에게 거슬러 줘야할 돈이 N원이라면 거슬러줘야 할 동전의 최소 갯수는?
N = int(input())
changes = [500, 100, 50, 10]
cnt = 0
for change in changes:
cnt += N // change
N %= change
print(cnt)
그리디 알고리즘의 정당성
이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는
가지고 있는 동전 중 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
예를 들어 800원을 거슬러줘야하는데 화폐 단위가 500원, 400원, 100원이라면 그리디 알고리즘의 경우 500+100*3 이지만 최적의 해는 400+400 이다.
대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야한다.
