이것이 취업을 위한 코딩 테스트다 with python - 나동빈님 책을 보고 작성하였습니다

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

그리디(Greedy) 알고리즘은 단순하지만 강력한 문제 해결 방법입니다.

이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘입니다. 여기서 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.
그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

보통 그리디 알고리즘의 유형의 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 합니다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됩니다.

이제 그리디 알고리즘을 대표하는 문제인 거스름돈 문제를 풀어보겠습니다.

1. 거스름돈 예제

손님에게 계산을 도와주는 상황입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한히 존재한다고 가정하겠습니다. 손님에게 거슬러 줘야할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구해야합니다. 이 때, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

1-1. 문제해설

거스름돈 예제는 가장 큰 화폐 단위부터 돈을 거슬러 주는것이 해설입니다. 만약 560원을 거슬러준다고 가정하겠습니다. 가장 먼저 500원을 거슬러 줄 수 있을 만큼 거슬러 줍니다. 그 후 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있습니다.

그러면 560원의 동전은 500원 한 개, 100원은 없고, 50원 한 개, 10원 한 개로 총 3개의 동전으로 거슬러 줄 수있습니다.

1-2. 소스코드

예제를 파이썬으로 짠 소스코드는 다음과 같습니다.

# 거슬러 줘야 할 금액 입력받기
n = int(input())
# 동전의 개수
count = 0

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

# 큰 화폐부터 차례대로 순환하며
for coin in coin_types:
    # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    count += (n // coin) # 거슬러 줄 돈을 화폐로 나눈 몫을 구한다
    # 그 후 해당 화폐를 나눈 나머지를 금액에 대입
    n %= coin

print(count)

2. 그리디 알고리즘의 정당성

그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 없습니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분합니다. 하지만 거스름돈 문제에서 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적입니다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야합니다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.

예를 들어 600원을 거슬러 줘야 하는데, 화폐 단위가 500원, 300원, 50원인 경우를 생각해보겠습니다. 이 경우 그리디 알고리즘으로는 (500원 1개 + 50원 2개)를 거슬러 주는 동전 총 3개가 나오는데 최적의 해는 (300원 + 300원)을 거슬러 주는 것입니다.

다시 말해 예제의 거스름돈 문제는 큰 단위가 작은 단위의 배수 형태이므로 그리디 알고리즘으로 해결이 가능한 것입니다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 아이디어를 떠올리고 정당한지 검토해야 답을 도출할 수 있습니다.