그리디 알고리즘 정리

👩‍💻 그리디 알고리즘 (탐욕법) 정리 with Python

🥝 그리디 알고리즘 (Greedy Algorithm)이란? 

1. 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식입니다.

 

2. 각각의 선택은 그 순간 보았을 때는 가장 좋아 보이지만 나중에는 최적의 해가 아닐 수 있습니다.

 

3. 즉 매 순간의 선택은 locally optimal 하지만 globally optimal하지 않습니다.

그렇기에 그리디 알고리즘으로 최적해를 얻을 수 없는 것이 존재합니다.

 

🍋 그리디 알고리즘 예시 1 - 동전 문제

지불해야 하는 값이 7870원 일 때 가장 적은 수의 돈으로 지불하는 방법을

그리디 알고리즘을 활용하여 구할 수 있습니다.
가장 큰돈부터 최대한 지불해야 하는 값을 채우는 방식으로 구현되며
그리디 알고리즘으로 매 순간 최적이라고 생각되는 경우를 선택하면 됩니다. 

 

🍊 동전 문제 코드

# Greedy1 - Coin Problem

coinList = [5000, 1000, 500, 100, 50, 10]


def greedy1(conList, value):
    conList.sort(reverse=True)
    totalCount = 0
    details = list()

    for i in conList:
        count = value // i
        totalCount += count
        value -= count * i
        details.append([i, count])

    return totalCount, details


print(greedy1(coinList, 7870))

 

🍉 그리디 알고리즘 예시 2 -  Fractional Knapsack Problem

무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제입니다.

각 물건은 무게 w와 가치 v로 표현될 수 있습니다.

물건을 쪼갤 수 있고 물건의 일부분을 배낭에 넣을 수 있습니다.

🍋 Fractional Knapsack Problem 코드

# Greedy2 - Fractional Knapsack Problem

dataList = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]


def knapsack(dataList, capacity):
    dataList = sorted(dataList, key=lambda x: x[1] / x[0], reverse=True)
    details = list()
    totalValue = 0

    for i in dataList:
        if capacity - i[0] >= 0:
            capacity -= i[0]
            totalValue += i[1]
            details.append([i[0], i[1], 1])
        else:
            fractions = capacity / i[0]
            totalValue += fractions * i[1]
            details.append([i[0], i[1], fractions])
            break
    return totalValue, details


print(knapsack(dataList, 30))

 

🥭 그리디 알고리즘의 한계

그리디 알고리즘은 반드시 최적의 해를 구할 수 있는 알고리즘이 아닙니다.

그 순간에 가장 좋아 보이는 선택을 통해 최적의 해에 가까운 값을 구하는 알고리즘입니다.

그렇기에 그리디 알고리즘으로는 최적해를 구할 수 없는 문제도 있습니다.

 

위 그래프에서 가장 작은 값을 찾아 leaf node까지 가는 경로를 찾는 문제에서...

그리디 알고리즘으로 가장 작은 값을 찾아 경로를 찾는다면 7 -> 12 = 19 일 것입니다.

하지만 실제로 가장 작은 값은 10 -> 5이며 15가 구하고자 하는 값입니다.