[Python] Greedy(그리디)

■

 

Greedy는 한국말로 "탐욕스러운"이라는 뜻이다. 따라서 그리디 알고리즘은 말 그대로 눈앞의 이익만 쫓는 아주 탐욕스러운 알고리즘이라는 것이다.

 

그렇다면 Dynamic Programming(다이나믹 프로그래밍)과 Greedy(그리디)는 무엇이 다른 걸까??

조금 딱딱하게 이론적으로 설명하자면 다이나믹 프로그래밍은 하위 문제에 대한 최적의 해결책을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션(global optimum solution)에 대한 선택을 하고 그리디는 각 단계마다 최적해를 찾는 문제로 접근해 문제를 작게 줄여나가는 형태이다.

 

이후 설명을 통해 좀 더 이해해보자.

 

■■

 

대표적인 매우 유명한 문제인 배낭 문제를 예제로 그리디 알고리즘을 구현해보겠다.

[출처]위키백과

위 그림과 같이 15kg을 담을 수 있는 배낭이있고 짐이 각각

 

	가격 ($)	단가	무게 (kg)
A	4	0.333	12
B	2	1	2
C	2	2	1
D	1	1	1
E	10	2.5	4

위 표와 같이 되어있다.

 

해당 배낭 문제는 $(달러)의 가치가 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

그리디는 아주 탐욕스럽고 욕심이 많은 알고리즘이기때문에 단가가 가장 높은 짐부터 차례대로 집어넣는다.

단가가 가장 높은 짐은 E이므로 E부터 순서대로 E, C, B, D를 담으면 총 8kg으로 남은 무게가 7kg이 된다.

하지만 남은 A의 무게는 12kg이기때문에 원래대로라면 가져가지 못하지만 그리디는 A를 7 / 12만큼 쪼개버려서 담아버린다.

 

자, 이제 짐이 cargo = [(4, 12), (2, 1), (2, 2), (1, 1), (10, 4)] 로 구성되어 있다고하고 코드로 구현해보자.

 

def greedy(cargo):
    #배낭의 무게 15 선언
    total_weight = 15
    #각 짐별 가격, 단가와 무게를 저장해둘 리스트를 선언해준다
    data = []
    
    for price, weight in cargo:
        data.append((price / weight, price, weight)) #단가, 가격, 무게를 각 짐별로 data에 넣어준다
    #가장 단가가 큰 짐부터 넣을 것이므로 내림차순 정렬한다
    data.sort(reverse = True)
    
    total_price = 0 #총 금액
    #단가가 높은 짐부터 차례대로 꺼낸다
    for unit_price, price, weight in data:
        #해당 짐의 무게가 배낭의 남은 무게보다 작거나 같다면 배낭에 넣어준다
        if total_weight - weight >= 0:
            total_weight -= weight
            total_price += price
        #해당 짐의 무게가 배낭의 남은 무게보다 크다면 쪼개버리고 넣어버린다
        else:
            fraction = total_weight / weight #배낭의 남은 무게만큼을 쪼갠 짐의 무게 계산
            total_price += price * fraction #쪼개진 짐의 무게의 가격 계산
            break #더 이상 배낭에 들어갈 수 없으므로 stop
            
    return total_price

 

■■■

 

한 가지 더, 그리디 알고리즘을 사용하지 못하는 예를 알아보자.

위 그림과 같은 이진 트리가 있다고 가정하자.

이 이진 트리에서 가장 큰 합을 찾아야한다고 하면 8 → 13 → 7 순서로 총 합 28을 출력하게 될 것이다.

정작 가장 큰 숫자인 50이 있는데도...

 

따라서 해당 이진 트리에 추가 작업을 하지 않는 이상 그리디 알고리즘으로 풀 수 없다.