Greedy Algorithms(탐욕법)

현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 그리디

---

:smile:

대표적인 예제 거스름돈

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

:rocket:

문제해설

당장 좋은 것 : “ 가장 큰 화폐 단위부터 돈을 거슬러 주는 것 ! “

예를 들어 N이 1,260이라면 500원 2개, 100원 2개, 50원 1개, 10원 1개로 모두 거슬러 줄 수 있다.

n = 1260
count = 0

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

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

print(count)

그리디 알고리즘의 정당성

코드를 보면 화폐의 종류만큼 반복을 수행한다. 따라서 시간 복잡도는 화폐의 종류가 k개라고 할 떄 O(k)이다. 즉 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다는 것을 알 수 있다.

그러나 항상 이렇게 거스름돈 문제를 쉽게 풀 수 있을 까??

NO:cry:

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 작은 단위의 배수이기 때문이다.

예를 들어 화폐 종류가 500, 400, 100 이고 거스름돈이 800원이라고 하면 (500, 100, 100, 100)이 맞을까? (400, 400)이 맞을 까? 후자가 맞다… 따라서 이 문제에서는 큰 단위가 작은 단위의 배수 형태 이므로 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인 하여 거슬러 주는 작업만 수행하면 된다

결론

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 컴토할 수 있어야 답을 도출 해낼 수 있음