그리디 알고리즘:판단하는 순간 가장 좋은 것을 고르는 방법

미래에 대해서 고려하지 않음.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시한다.

 

 

예제 - 거스름돈

카운터에는 거스름돈으로 사용할 500, 100, 50, 10원이 무한히 존재한다고 가정. 손님에게 거슬러줘야할 돈이 N원인 경우 거슬러 줘야할 동전의 최소 개수를 구하라. (단, N은 항상 10의 배수이다.)

 

거스름돈 문제는 그리디 알고리즘으로 풀 수 있는 대표적 문제로, 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.

기준 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 것.

 

n=1260
count=0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n//coin # '//'은 몫을 구하는 연산자
    n %=coin

print(count)

 

그리디 알고리즘의 정당성

그리디 알고리즘으로 해법을 찾았을 때에는 그 해법이 정당한지 검토해야한다. ( 최적의 해가 아닐 수 있음)

위의 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 단위가 더 큰 동전은 항상 작은 단위 동전의 배수이기 때문이다. 그렇지 않으면 작은 단위의 동전을 종합해 다른 해가 나올 수 있다.

 

800원을 거슬러줘여하는 경우, 동전의 단위가 500 400 100이라고 하면 그리디 알고리즘으로 나오는 해는 500 + 100*3으로 4개이다. 그러나 최적 해는 400*2로 2개이다.

 

그러므로 그리디 알고리즘을 사용할 때, 해당 문제에 대해 사용하는 것이 정당한지 검토할 수 있어야한다.