그리디 알고리즘

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

 

사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형

 

문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다.

(그래서 주로 정렬 알고리즘과 짝을 맞춰 출제되기도)

 

대표적인 예시 문제

거스름돈 계산하기 -> 가장 큰 화폐 단위부터

Q. 거스름돈이 1260원일때, 500, 100, 50, 10원을 이용해 몇개씩 주면 될지 계산하라

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)