[알고리즘] 탐욕 알고리즘

1. 탐욕 알고리즘 이란?

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

2. 탐욕 알고리즘 예

문제1: 동전 문제

• 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.
  - 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
  - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

coinList = [1, 100, 50, 500]

def countCoin(value, coinList):
    totalCnt = 0 # 총 동전의 수
    result = list() # 어떤 동전이 몇 개 사용되었는지
    coinList.sort(reverse = True)
    for x in coinList:
        quotient = value // x
        totalCnt += quotient
        value = value % x # value 갱신
        result.append([x, quotient])
    return totalCnt, result

print(countCoin(4720, coinList)) # (31, [[500, 9], [100, 2], [50, 0], [1, 20]])

문제2: 부분 배낭 문제 (Fractional Knapsack Problem)

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

참고
Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함 (0/1 Knapsack Problem 으로 부름)

items = [(10,10), (15,12), (20,10), (25,8), (30,5)] # tuple: (무게, 가치)

def calcMaxValue(items, maxWeight):
    maxValue = 0 # 최대 가치
    result = list() # 담긴 물건들의 정보 리스트 (무게, 가치, 비율)
    items.sort(key=lambda x: x[1]/x[0], reverse=True) # 무게 대비 가치가 높은 순으로 정렬
    
    for x in items:
        if x[0] <= maxWeight:
            maxValue += x[1]
            maxWeight -= x[0]
            result.append([x[0], x[1], 1]) # 1개를 모두 넣은 것
        else:
            fraction = maxWeight / x[0]
            maxValue += x[1] * fraction
            result.append([x[0], x[1], fraction]) # 쪼개서 넣은 것
            break # 더이상 물건이 들어갈 수 없으니 반복문 종료
    return maxValue,result

print(calcMaxValue(items, 30)) # (24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])

3. 탐욕 알고리즘의 한계

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

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기