[알고리즘 / Algorithm] chapter 3. Greedy Algorithm (그리디 알고리즘)

출처 : 이것이 취업을 위한 코딩 테스트다  with  파이썬(나동빈 저 / 한빛미디어)  

Greedy Algorithm (그리디 알고리즘) 

 

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

그리디 알고리즘을 번역하면 '탐욕적인' 알고리즘이다. 여기서 '탐욕적' 이라는 말은 현재 상황에서 지금 당장 좋아보이는 것만 고르는 방법을 의미한다. 

 

그리디 알고리즘은 문제의 유형이 매우 다양하기 때문에 암기해서 잘 푼다고 할 수 없다.

대신 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야한다.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로' , '가장 작은 순서대로' 와 같이 기준을 은근슬쩍 제시해준다. 대체로 그리디 알고리즘은 정렬 알고리즘과 짝을 이뤄 출제가 된다.

 

 

 

예제 3-1 거스름돈

<문제>

카운터에 거스름돈 500원, 100원, 50원 10원이 무한히 존재한다. 손님에게 거슬러줘야하는 거스름돈이 N원일 때, 동전의 최소의 개수는? (N은 항상 10의 배수이다.) 

 

<아이디어> 

거슬러줄 동전을 최소로 하려면, 큰 돈을 먼저 거스름돈으로 주면 된다.

거스름돈이 1200원이라면, 100원짜리 동전 12개 주는거보다 500원짜리 동전 2개와 100원짜리 동전 2개 주는게 더 적다.

 

<해결방법>

1. 일단 거스름돈을 내림차 순으로 정렬한 후, 리스트에 담는다.

2. for문을 사용해 거스름돈을 하나씩 꺼내서 나눈다.

3. count라는 새로운 변수를 선언해 나눈 몫을 계속 더한다.

4. 거스름돈으로 나눈 나머지를 다시 N으로 넣어 2번부터 3번의 과정을 반복한다.  

 

<코드>

N = int(input())
count = 0  
coin_list = [500,100,50,10] #내림차순으로 담는다.

for coin in coin_list:
	count += N//coin
    	N = N%coin
    
print(count) 

그리디 알고리즘의 정당성 

그리디 알고리즘은 최적의 해를 찾을 수 있을 때 가장 효과적인 알고리즘이다.

위 예제처럼 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 효과적이고 직관적이다. 

 

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

위 예제처럼 거스름돈 문제를 그리디 알고리즘으로 풀 수 있었던 이유는 가지고 있는 동전 중 큰 단위(500원)가 항상 작은 단위(10원)의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 

만약 작은 단위위의 동전이 4원, 1원 이런 돈이였다면 이러한 단위를 종합해 다른 해가 나올 수 있다. 이런 경우는 그리디 알고리즘은 적합하지 않다. (그리디 알고리즘이 최적의 결과를 가져오지 않을 수 있음) 

 

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