Greedy

주로 교제에서 "탐욕법"이라고 소개되는 그리디(Greedy) 알고리즘은 단순하면서 강력한 해결 방법이다.

탐욕법이라고 불리는 이유는 미래 상황을 생각하지 않고 단순히 현재 상황에서 제일 최선의 것을 고르기 때문이다. 즉 현재의 상황에서만 고려하고 이 선택이 미래에 불러올 영향에 대해서는 전혀 고려하지 않는다.

 

그리드 알고리즘은 최적의 해를 도출한 가능성이 낮다. 현재의 상황에 대해서만 판단하기 때문에 주기가 긴 코드에 대해서 현재의 선택이 미래에 악영향을 끼칠 가능성이 크기 때문이다. 따라서 그리디 알고리즘을 통해서 문제해결책을 세웠다면, 그 해법이 옳은지 검증해야 한다. 

아래에 나올 동전 문제에 대해서는 동전 중 큰 단위가 항상 작은 단위의 배수임이 확신되므로, 작은 단위의 동전을 종합해 다른 해가 나올수 없어서 "그리디 알고리즘"이 최선의 선택을 한다는 것을 보증할 수 있다. 

 

 

 

 

예제 : 500원 동전과 100원 동전, 10원 동전이 무한하게 존재하며, 손님에게 현금을 받고 거슬러줘야 할 돈이 ?원인 경우,  거스름돈으로 거슬러 줄 수 있는 동전의 최소 개수를 구하여라. 단, 거스름 돈은 항상 10의 배수이다. 

 

솔루션 :  가장 간단한 해결 방법은 그리디 알고리즘을 사용해 문제를 해결하는 것이다.  

동전을 선택할 때 마다 가장 큰 값의 화폐를 몇개 선택할 수 있을지 고른 후 그다음으로 넘어가고 이를 반복하여 가장 큰 동전의 단위부터 돈을 거슬러 주는 것이다. 이런식으로 진행하면 동전은 항상 배수의 관계이기 때문에 총 거슬러 주는 동전이 최소의 동전개수로 거슬러 줄 수 있다. 

 

 

거스름돈이 1470원이라고 할 때 "그리디 알고리즘"을 이용하여 문제를 해결해 보자 

 

	손님에게 준 돈	거스름돈 - 현재 돈	손님이 가진 현재 동전
STEP 1   ( 500 원 )	500 x 2	470	500 x2
STEP 2   ( 100 원 )	100 x 4	70	500 x2, 100 x4,
STEP 3   ( 50 원 )	50 x 1	20	500 x2, 100 x4, 50 x1
STEP 4   ( 10 원 )	10 x 2	0	500 x2, 100 x4,  50 x1, 10 x2

 

각 단계별로 배수의 관계인 큰 화폐별로 손님에게 거스름 돈을 준다면 손님이 받을 거스름돈은 최소 개수임이 보장된다.

예를 들어 1000원을 거슬러 줄 때 500원 2개를 거슬러 주는 것보다, 100원 짜리 10개를 거슬러 주는 것은 최소 개수에서의 오류임으로 각 단계에서 최대로 줄 수 있는 동전 개수를 거슬러 준다면 그리디 솔루션으로 문제를 해결하는 것이 정당해진다.

 

이를 코드로 풀어 내면 아래와 같다. ( 코드는 파이썬으로 기술 하였다 )

x = 1470 money_count = 0 coin_kinds = [500, 100, 50, 10] for coin in coin_kinds:     coin += n // coin      n %= coin  print( "최소 동전의 갯수는 {0} 입니다".format(money_count) )

 

 

 

하지만 각 동전이 배수의 관계가 아닌 상황이라면 그리디 해결법을 사용할 수 없다. 예를 들어 1000원짜리 거스름돈에 거슬러 줄 수 있는 동전이 550 210 200 50 10 이런식으로 존재한다면 그리디 솔루션으로는  550, 210 x2 , 10 x3  총 6개의 동전이 필요하지만 210원을 고르지 않는다면 550 200x2 50 총 4개의 동전만으로 거스름돈을 해결 할 수 있다. 따라서 이 경우에는 같은 방식으로 짠 그리디 해결법이 최선의 선택을 하는 것을 보증하지 못한다.

 

위와 같이 그리디 알고리즘에서는 문제를 해결 할 방법을 떠올렸다면 그 아이디어가 정당한 방법인지 검토하여서 옳은 방법일때 알고리즘을 적용하는 것이 현명하다.