Python 52 - 당장 좋은 것만 선택하는 그리디 ( 알고리즘 )

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

이 알고리즘 유형은 국내 알고리즘 교재에서 단어그대로 번역하여 '탐욕법' 으로 소개된다.

이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 

여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.

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

그리디 알고리즘 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다.

사전 지식 없이도 풀 수 있는 문제 도 있겠지만, 많은 유형을 접해보고 문제를 풀어보며 훈련해야 한다.

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

 

문제

당신은 음식점의 계산을 도와주는 점원이다.

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러 줘야하 할 돈이 N원 일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

문제해설

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다. 그것은 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다. N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러준다. 그다음 100원, 50원, 10원 짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다. 예를 들어 입력으로 주어진 N이 1,260 이라면 다음과 같이 가장 큰 화폐 단위부터 거슬러 주는 과정을 통해 1,260원을 모두 거슬러 줄 수 있다. 아래 사진을 참고해서 이해해보도록 하자.

답안

n = 1260
count = 0

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

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

그리디 알고리즘의 정당성

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

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해' 를 찾을 수 없을 가능성이 다분하다.

하지만 거스름돈 문제에서 '가장 큰 화폐단위부터' 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근 했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야한다.

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 대부분의 그리디 알고리즘 문제에서는 이처럼 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding