[python | 파이썬] Greedy Algorithm | 그리디 알고리즘

그리디 알고리즘은 말그대로 "탐욕법" 즉, 현재 상황에서 지금 당장 좋은 것만을 고르는 방법을 의미한다.

 

그리디의 대표적인 문제인 거스름돈 문제를 살펴보자.

5585번: 거스름돈

 

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 가장 대표적인 문제로, 가장 큰 화페 단위부터 돈을 거슬러 주는 방식으로 해결할 수 있다.

coins = [500, 100, 50 , 10, 5 , 1]
n = int(input())

money = 1000-n
cnt = 0

for coin in coins:
  cnt += money // coin
  money %= coin

print(cnt)

위 문제가 그리디 알고리즘으로 풀리는 이유는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.