그리디 알고리즘

 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다.

 

 그리디 알고리즘이란 바로 눈앞의 이익만을 쫒는 알고리즘을 말한다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘은 최적화 문제를 대상으로 한다.

 

 그리디 알고리즘은 최적 부분 구조 문제를 푼다는 점에서 흔히 다이나믹 프로그래밍과 비교되는데, 서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근 방식 또한 다르다.

 

 그리디 알고리즘을 중심으로 풀 수 있는문제, 다이나믹 프로그래밍으로 풀어야 하는 문제, 그리디 알고리즘으로는 풀 수 없는 문제들에 대해 차례대로 살펴보자.

 

 배낭 문제

 배낭 문제는 조합 최적화 분야의 매우 유명한 문제로, 다음 그림과 같이 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 각각 짐의 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록, 즉 달러의 가치가 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

 배낭 문제는 그림 21-1과 같이 짐을 쪼갤 수 있는 경우인 분할 가능 배낭 문제와 짐을 쪼갤 수 없는 경우인 0-1배낭 문제로 나뉜다.

 이 경우 단가가 가장 높은 짐부터 차례대로 채워나간다. C의 단가가 2.5달러로 가장 높으므로 C,B,E,D 순으로 총 8kg의 짐을 배낭에 담고 마지막 남은 7Kg을 위해 A의 7/12만큼을 쪼개서 배낭에 그리디 알고리즘으로 담는다.

 

 이제 단가 순으로 그리디 알고리즘으로 계산하면 된다.

cargo=[
    (4,12),
    (2,1),
    (10,4),
    (1,1),
    (2,2)
]
def fractional_knapsack(cargo):
    capacity=15
    pack=[]
    
    for c in cargo:
        pack.append((c[0]/c[1],c[0],c[1]))
    pack.sort(reverse=True)
    
    # 단가 순 그리디 계산
    total_value=0
    for p in pack:
        if capacity - p[2] >=0:
            capacity -= p[2]
            total_value += p[1]
            
        else:
            fraction=capacity/p[2]
            total_value +=p[1] * fraction
            break
        
    return total_value

r=fractional_knapsack(cargo)
print(r)

 이처럼 구현했을때 total_value는 17.3을 구할 수 있다. 그러나 만약 짐을 쪼갤 수 없다면 지금까지 실행한 방식대로 단가 순으로 배치해선 안 된다. 

 

 동전 바꾸기 문제

 동전의 액면이 10원, 50원, 100원처럼 증가하면서 이전 액면의 배수 이상이 되면 그리디 알고리즘으로 풀 수 있다. 예를 들어 160원을 거슬러 준다면 10원짜리 16개보다는, 100원짜리 하나, 50원 짜리 하나, 10원 짜리 하나로, 각각의 동전을 최대한 활용하는 그리디한 방법이 가장 작은 동전 개수로 거슬러줄 수 있는 방법이다.

 

 그런데 만약 다른 나라에 갔더니 80원 짜리 동전이 더 있다고 치자, 이 경우 더 이상 그리디하게 풀 수 없다. 이 경우 다이나믹 프로그래밍으로 풀어야 한다.

 

 가장 큰 합

 세 번째로는, 그리디 알고리즘의 실패 사례를 살펴보자. 노드를 계속 더해가다가 마지막에 가장 큰 합이 되는 경로를 찾는 문제다.

 이 문제는 이진 트리를 정렬한다든지 등의 추가 작업을 하지 않는 한, 그리디 알고리즘으로는 풀이할 수 없다.