탐욕 알고리즘

---

• 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘이다.
• 여러 경우 중 하나를 결정해야할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식이다.

탐욕 알고리즘의 한계

---

• 탐욕 알고리즘은 근사치 추정에 활용된다.
  • 반드시 최적의 해를 구할 수 있는 것은 아니기 때문이다.
• 최적의 해에 가까운 값을 구하는 방법 중의 하나이다.

예시

• '시작' 노드에서 시작해서 가장 작은 값을 찾아 leaf node까지 가는 경로를 찾아라.
  • Greedy 알고리즘을 적용하면 시작 -> 7 -> 12를 선택하게 된다. 값은 19가 된다.
  • 하지만, 실제 가장 작은 값은 시작 -> 10 -> 5이며, 가장 작은 값은 15이다.

탐욕 알고리즘 예제

---

동전 문제

• 지불해야 하는 값이 4720원 일 때, 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.
  • 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 풀면 된다.

def minCountCoin(value, coin_list):
    total_count = 0 # 동전의 총 개수
    detail = list() # 어떤 동전이 몇 개 들어갔는지 확인
    coin_list.sort(reverse = True)
    
    for coin in coin_list:
        coin_num = value // coin
        value -= coin * coin_num
        total_count += coin_num
        detail.append([coin, coin_num])
    return total_count, detail

테스트

coin_list = [50, 100, 1, 500]
value = 4720
print(minCountCoin(value, coin_list))

# 출력
(31, [[500, 9], [100, 2], [50, 0], [1, 20]])

부분 배낭 문제

• 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제이다.
  • 각 물건은 무게(w)와 가치(v)로 표현될 수 있다.
  • 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있다.

def getMaxValue(capacity, data_list):
    total_value = 0
    detail = list()
    # 가치가 무게에 어느 정도 비율을 차지하는 지 구한 후 내림차순으로 정렬한다.
    data_list.sort(key = lambda x: x[1] / x[0], reverse = True)
    
    for thing in data_list:
        if capacity >= thing[0]:
            capacity -= thing[0]
            total_value += thing[1]
            detail.append([thing[0], thing[1], 1])
            if capacity == 0:
                break
        else:
            fraction = capacity / thing[0]
            total_value += thing[1] * fraction
            detail.append([thing[0], thing[1], fraction])
            break
    return total_value, detail

테스트

data_list = [(10,10), (15, 12), (20, 10), (25, 8), (30, 5)]
print(getMaxValue(24, data_list))

# 출력
(21.2, [[10, 10, 1], [15, 12, 0.9333333333333333]])