그리디 알고리즘

 매 순간 최적의 경우만을 고려하는 방법. 

현실 속 당장의 문제를 해결해주는 후보에게 표를 던지거나 당장 눈 앞의 마쉬멜로를 먹는 행위

ex)

가능한 짧은 경로를 고를 때, 전체 경로 중 최적의 값을 고려하는 대신에 매 선택지 중 가장 짧은 도로를 고른 경우의 합. 
각 경로의 선택이 1-1-100 vs 최적의 경로 10 -10 -30 

최적해들의 집합이 곧 전체의 해답이 되는 경우 사용 가능! 


이경우는 최적해가 아님
: 각 선택이 다음 선택에 영향이 없어야 함

사용 사례 :  거스름돈 문제, 다익스트라, 허프만, 제약 조건이 많은 경우 등 

 

 

거스름돈 문제 예시 코드

n = 1260
count = 0


coin_types = [500, 100, 50, 10]
for coin in coin_types：
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기 n %= coin
print（count）

내 코드 

n = int(input())
cnt = 0 

while n >= 500:
    n -= 500
    cnt += 1
 
while n >= 100:
    n -= 100
    cnt += 1

print(cnt)