[Algorithm] 탐욕적인 알고리즘, Greedy

이번 글은 눈 앞에 보이는 최선의 선택만 하는 알고리즘 Greedy 알고리즘에 관한 내용입니다.

 

탐욕스런 알고리즘, Greedy

Greedy 알고리즘은 이전에 다뤘던 Dynamic Programing 이나 Divide and Conquer 알고리즘처럼 사용하기 위한 필수 조건이 있는 것은 아닙니다. 하지만 미래는 내다보지 않고 눈 앞에 보이는 최선의 선택만 하는 탐욕적인 알고리즘이기 때문에 최적의 답을 찾기 위한 조건은 있습니다. 최적의 부분 구조를 갖고 각 단계에서 탐욕스러운 선택이 각 문제에서 최종 답을 구하기 위한 최선의 선택이라는 탐욕적 선택 속성을 갖고 있다면 최적의 답을 보장할 수 있습니다.   

 

간단하고 빠르다는 장점을 갖고 있지만 최적의 답을 보장해주는 조건에 사용하는 것이 아니라면 최적의 답을 보장받지 못한다는 단점을 갖고 있습니다. 그래서 다른 알고리즘이 너무 느리거나 최적의 답이 필요없을 때 사용하기도 합니다. 

 

Greedy 알고리즘의 대표적인 예제는 '거스름돈 걸러주기' 입니다. 

 

500원, 100원, 50원, 10원이 있을 때 140원을 걸러줘야합니다. 이때, 가작 적은 동전의 수로 거스름돈을 걸러주려면 어떻게 할 수 있을까요?

500원

100원

50원

10원

 

가장 큰 동전인 500원을 2개, 그 다음 동전임 10원을 4개 이용하는 것이 가장 적게 나눠주는 경우입니다. 이는 가장 큰 동전부터 사용해서 거슬러주는 탐욕적 선택 속성을 갖고 있는 경우입니다. 하지만 100원, 70원, 50원, 10원이 있는 경우에 140원을 거슬러줘야한다면 어떻게 나눠줄 수 있을까요? 

100원

70원

50원

10원

70원 2개를 사용하는 것이 가장 적은 동전의 수를 이용하는 경우입니다. 이때, 탐욕적 선택 속성을 갖고 있지 않아 Greedy 알고리즘을 사용한다면 100원 1개, 10원 4개를 사용하게 됩니다. Greedy 알고리즘을 사용했을 때 최적의 답을 보장해주지 않는 사례 중 하나입니다. 이처럼 문제에서 최적의 부분 구조인지, 탐욕적 선택 속성을 갖고 있는지 확인하고 알고리즘을 적용해야합니다. 

 

가장 적은 수의 동전으로 거스름돈을 돌려주는 거스름돈 문제를 코드로 작성해보겠습니다. 

 

def min_coin_count(value, coin_list):
    
    count = 0
    
    for coin in reversed(sorted(coin_list)):  # 가장 큰 동전부터 나눠줄 수 있도록 정렬 
        
        count += value//coin  # 가장 큰 동전을 몇 개 사용하는가
        
        value %= coin #남은 금액 
        
    return count