[파이썬 알고리즘 인터뷰] 그리디 알고리즘

그리디 알고리즘(Greedy Algorithm)이란 눈앞의 이익만을 좇는 알고리즘이다.

• 잘 작동하는 문제들은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다.
  • 탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는 것
  • 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성

다익스트라 알고리즘은 대표적인 그리디 알고리즘의 예로서 최적해를 찾을 수 있으며 압축 알고리즘인 허프만 코딩 알고리즘은 허프만 트리를 빌드할 때 그리디 알고리즘을 사용하며, 마찬가지로 최적해가 보장된다.

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

• 다이나믹 프로그래밍이 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 함
• 그리디 알고리즘은 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태로, 서로 반대 방향으로 접근하는 구조를 띤다.

배낭 문제

배낭 문제는 조합 최적화 분야의 매우 유명한 문제이다.

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고 각각 짐의 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록, 즉 가치가 최대가 되도록 짐을 고르는 방법을 찾는 문제다. 이 문제의 풀이 방법은 단가가 가장 높은 짐부터 차례대로 채워나가면 된다.

그리디 vs 다이나믹

배낭 문제에서 짐을 쪼갤 수 있다면 그리디 알고리즘으로 해결이 가능하지만 짐을 쪼갤 수 없으면 다이나믹 프로그래밍으로 해결해야한다.

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: float = 0
    for p in pack:
        if 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

cargo = [
    (4, 12),
    (2, 1),
    (10, 4),
    (1, 1),
    (2, 2),
]

r = fractional_knapsack(cargo)

동전 바꾸기 문제

동전 바꾸기 문제도 그리디 알고리즘 문제로 유명하다. 동전의 액수가 10원, 50원, 100원처럼 이전 액수의 배수로 증가하기 때문에 그리디로 해결가능하다.

이전 액수의 배수로 증가하지 않는 경우(ex. 50원, 80원, 100원)에는 다이나믹 프로그래밍으로 풀어야 한다.

가장 큰 합

트리의 노드를 계속 더해가다가 마지막에 가장 큰 합이 되는 경로를 찾는 문제에서는 이진 트리를 정렬하는 추가 작업 등을 해야지 그리디 알고리즘으로 풀이가 가능하다.