[Python] 그리디 알고리즘

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

단순히 가장 좋아 보이는 것을 반복적으로 선택하는 최소한의 아이디어를 떠올린 후 최적의 해를 구할 수 있는지 검토해야 한다.

 

문제 1. 거스름돈

백준 온라인저지(BOJ) 5585번

5585번: 거스름돈

- 답 확인

money = 1000 - int(input())

coins = [500, 100, 50, 10, 5, 1]
changes = 0
result = 0

for coin in coins:
  result += money // coin
  money %= coin
  if money == 0: break

print(result)

- 시간 복잡도

거스름 돈의 금액과는 무관하고 화폐 종류의 개수에 영향을 받는다.

그러므로 화폐의 종류가 K개일 경우 시간 복잡도는 O(K)가 된다.