Chapter 3-1 당장 좋은 것만 선택하는 그리디

< 이 글은 책 '이것이 취업을 위한 코딩 테스트다' 에서 발췌한 내용을 인용했습니다. >

 

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

 

'사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제유형'이며 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘을 대표하는 문제로 '거스름돈' 문제가 있다.

예제 3-1 거스름돈

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

 

<무지성 코드>

n = int(input()) # 거슬러 줘야 할 돈
count = 0 # 동전의 개수

while(n >= 500):
    n -= 500
    count += 1
while(n >= 100):
    n -= 100
    count += 1
while (n >= 50):
    n -= 50
    count += 1
while(n >= 10):
    n -= 10
    count += 1
    
print(count)

 

<나동빈님의 코드>

n = int(input())
count = 0

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

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

print(count)

 

그저 코드만 봐도 짬의 차이가 느껴진다. 

우선 카운트는 지금껏 +1만 했었던 나 자신을 반성했다.

그리고 비슷한 부분들이 반복되는(복붙으로 값만 조금씩 바꾼)코드는 더 아름답게 바꿀 수 있는 방법이 있다는 것을 깨달았다. 지금은 공부하는 단계니 코드짜는 시간에 연연하기보다는 어떻게 하면 더 좋은 코드를 짤 수 있을지 고민하는데 시간을 더 사용해보자.

 

 

그리디 알고리즘의 정당성

 

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 다시 말해 이 문제에서는 큰 단위가 작은 단위의 배수 형태이므로, '가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다.'는 아이디어는 정당하다. 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.