Greedy

설명

현재 상황에서 지금 당장 좋은 것만 고르는 것

그리디 알고리즘의 정당성

그리디 알고리즘으 적용할 때는 이 해법이 정당한지 검토해야한다.

Exapmle

1. 거스름돈 500원, 100원, 50원, 10원을 사용하여 거슬러진 동전의 수를 최소화 하는 것

n = int(input())

coin = [500, 100, 50, 10]
coin_num = 0
for c in coin:
    coin_num += n // c
    n %= c

print(coin_num)

관련 알고리즘

• <이것이 코딩 테스트다>에서 언급된 Greedy 관련 알고리즘
  • Floyd-Warchall : 최단 경로
  • Eijkstra : 최단 경로