[Algorithm] 그리디 (Greedy)

그리디(Greedy)는 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘으로, 단순하지만 강력한 문제 해결 방법입니다.

 

즉, 그리디 알고리즘은 매 순간 가장 좋아 보이는 것을 선택하기 때문에 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

그리디 알고리즘을 이용한 문제 출제는 폭이 매우 넓기 때문에, 다익스트라(Dijkastra) 알고리즘과 같은 특별한 경우를 제외하고는 단순 암기를 통해 모든 문제를 해결하기는 어렵습니다.

 

따라서, 그리디 알고리즘이 적용 가능한 문제인지 아닌지 판단하고 실제로 풀어낼 수 있는 능력이 중요합니다.

참고로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같이 기준에 따라 선택하는 내용이 나온다면 보통 그리디 알고리즘으로 해결할 수 있습니다.

 

그리디 알고리즘의 대표 유형 문제인 '거스름돈' 문제를 보겠습니다.

 

<문제>

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

 

 

<해설>

거스름돈 문제는 '가장 큰 화폐 단위부터' 돈을 거슬러 주는것이 포인트입니다.

최소한의 동전을 사용해서 거슬러 줘야하기 때문에 가장 큰 단위인 500원으로 거슬러 줄 수 있을 만큼 거슬러 줍니다.

그리고 나서 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있습니다.

예를 들어 N이 1,260원 일때 500원 2개, 100원 2개, 50원 1개, 10원 1개로 총 6개의 동전으로 거슬러 줄 수 있습니다.

 

가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이기때문에 작은 단위의 동전들을 조합해 다른 해가 나올 수 없기 때문입니다.

예를 들어 N이 800이고 화폐 단위가 500원, 400원, 100원이면 그리디 알고리즘은 500원 1개, 100원 3개로 총 4개의 동전 개수를 리턴하지만 사실 최적의 동전 개수는 2개(400원 2개)입니다.

 

따라서 그리디 알고리즘은 문제 풀이를 위한 최소한의 아이디어를 떠올리고 그것이 정당한지 검토할 수 있어야 합니다. 

 

 

<구현>

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

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

print(count)

 

참고: https://www.youtube.com/watch?v=2zjoKjt97vQ&list=RDCMUChflhu32f5EUHlY7_SetNWw&index=3