탐욕 알고리즘

개요

목표

대상이 되는 문제들

탐욕 선택 속성을 갖는 최적 부분 구조인 문제들

그리디 알고리즘이 잘 작동하는 예

다이나믹 프로그래밍과의 비교

그리디 다이나믹 프로그래밍
부분 최적해로 전체 최적해를 찾으려는 문제해결 휴리스틱 겹치는 부분 문제와 최적의 하부 구조 속성을 가진 문제들을 푸는 데 도움을 주는 알고리즘
덜 효율적이다 더 효율적이다
처음 선택 시 최선으로 보이는 것으로 부분 문제들을 해결 모든 부분 문제를 풀고 최적 솔루션을 찾는 데 도움을 주는 하나를 선택
첫 단계를 고려하여 의사 결정 모든 단계에서 의사 결정

배낭 문제(Knapsack Problem)

분할 가능 - 그리디 알고리즘

항목 $ kg 단가
A 4 12 0.33
D 1 1 1
E 2 2 1
B 2 1 2
C 10 4 2.5 
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 capacity - p[2] >= 0:
            # 항목 전체를 그대로 넣을 수 있는 경우
            print('in if capacity: {}, p: {}'.format(capacity, p))
            capacity -= p[2] # 담을 무게만큼 배낭 무게 제거
            total_value += p[1]
        else:
            # 항목 전체를 그대로 넣을 수 없는 경우 분할
            print('in else capacity: {}, p: {}'.format(capacity, p))
            fraction = capacity / p[2]
            total_value += p[1] * fraction
            break
    return total_value

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

분할 불가능 - 다이나믹 프로그래밍

동전 바꾸기 문제

주어진 금액이 되는 최소 동전 수를 찾는 문제

# https://www.geeksforgeeks.org/greedy-algorithm-to-find-minimum-number-of-coins/
def findMin(money, monetary_units):
    n = len(monetary_units)
    ans = []
    # Traverse through all denomination
    i = n - 1
    while(i >= 0):
        # Find denominations
        while (money >= monetary_units[i]):
            money -= monetary_units[i]
            ans.append(monetary_units[i])
        i -= 1

    return ans

print(findMin(160, [10, 50, 100]))
print(findMin(160, [10, 50, 80, 100])) # 최적해 아니다

가장 큰 합

노드를 계속 더해가다가 마지막에 가장 큰 합이 된느 경로를 찾는 문제

        7
        └───┐
    3       12
             └─┐
  99  8    5   6