당장 좋은 것만 선택하는 그리디

Greedy 알고리즘이란?

• 단어 그대로 번역하면 '탐욕법'이다. (욕심쟁이 알고리즘이라고도 한다)
• 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
• 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
• 매 순간 가장 좋아 보이는 것을 선택하며 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘 팁

• 기준에 따라 좋은 것을 선택하는 알고리즘으므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
• 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제한다.
• 정렬, 최단 경로 등의 알고리즘 유현은 이미 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 있지만 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 다익스트라 알고리즘과 같은 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기 어렵다.
• 코딩 테스트에서 만나게 될 그리디 알고리즘 문제 유형은 '사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형'이라는 특징이 있다.
• 그래서, 많은 유형을 접해보고 문제를 풀어보며 훈련하는 편이 좋다.
• 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
• 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.
• 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민해보는 것도 한 방법이다.

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈을 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

예제

입력

1260

출력

6

풀이

n = int(input())
count = 0

mylist = [500,100,50,10]

for coin in mylist:
    count += n//coin
    n%=coin

print(count)

문제해설

그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제 해결 가능
'가장 큰 회폐 단위부터' 돈을 거슬러 주는 것
코딩테스트에서는 거스름돈 문제보다는 일반적으로 난이도가 높게 출시됌. 하지만 접근 방식이 유사하므로 그리디 알고리즘을 설명할 때 자주 소개되는 문제