탐욕 알고리즘

탐욕 알고리즘의 이해

1. 탐욕 알고리즘 이란?

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

2. 탐욕 알고리즘 예

문제1: 동전 문제

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

coin_list = [1, 100, 50, 500]
print (coin_list)
coin_list.sort(reverse=True)
print (coin_list)

[1, 100, 50, 500]

[500, 100, 50, 1]

coin_list = [500, 100, 50, 1]

def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse=True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details

min_coin_count(4720, coin_list)

(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 으로 부름)

      

       

위의 표를 (무게, 가치) 순으로 튜플을 원소로 하는 리스트를 만든다

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

 가치/무게로 가치가 높은 순으로 데이터를 정렬한다.

data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True)

sorted 함수에 첫번째 매개값으로 데이터 리스트를 주고, 두번째 매개값으로 데이터를 정렬할 조건을 준다.

lambda x에 서 x는 리스트의 원소인 튜플을 말하고 x[1]은 가치 x[0]은 무게이다. 세번째 매개값으로 내림차순(가치가 큰것부터 정렬)을 주었다.

 

data_list에 이미 정렬이 된 상태로 들어가 결과값은 똑같다.

def get_max_value(data_list, capacity):
    data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True)
    #sorted에 (리스트, 정렬하고 싶은 기준(가치를 무게로 나뭄), 큰수정렬)
    total_value = 0 	#얼만큼의 가치 되는지 알기위해
    details = list()	#어떤 가치의 물건이 얼만큼 들어갔는지 확인하기 위해
    
    for data in data_list:
        if capacity - data[0] >= 0:
            capacity -= data[0]
            total_value += data[1]
            details.append([data[0], data[1], 1])
        else:
            fraction = capacity / data[0]
            total_value += data[1] * fraction
            details.append([data[0], data[1], fraction])
            break
    return total_value, details

전체 가치를 확인할 수 있는 total_value 변수를 만들고, 어떤 물건이 얼만큼 들어가있는지 확인하기 위해 details 리스트를 만든다.

for data in data_list 에서 이미 리스트는 가치가 큰 순으로 정렬이 되어있기 때문에 젤 첫 data는 가치가 제일 크다.

  if capacity - data[0] >= 0: ▶만약에 가방의 용량에서 첫번째 물건의 무게를 빼고도 값이 남는다면

  capacity -= data[0] ▶가방의 용량은 첫번째 물건의 무게만큼 빼준다.( 가방에 물건을 넣었기 떄문)

  total_value += data[1] ▶가방에 들어간 물건의 가치만큼 가치를 카운트 한다.

  details.append([data[0], data[1], 1]) ▶ detaill리스트에 물건의  무게와  가치를  넣고  온전히 들어갔다는 의미에서 1을표시

 

만약 가방의 용량이 물건 하나를 다 담기에 모자라다면 물건을 가방에 들어갈 수 있는 무게로 쪼개야 한다.

  fraction = capacity / data[0] ▶ 가방의 여유 용량을 물건의 무게로 나눈다.

(남은 용량이 5이고 물건 무게가 20이라면 물건의1/4을넣을수있다.)

  total_value += data[1] * fraction ▶무게가 줄었기 때문에 가치도 그에 비례해 줄어야한다.

  details.append([data[0], data[1], fraction]) ▶디테일에 추가한다.

  break ▶더이상 물건을 넣을수 없으므로 반복을 멈춘다.

 

만약 배낭에 무게를 30까지 넣을수 있다면 .

get_max_value(data_list, 30)

 

Out[20]:

(24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])

총 가방에 들어간 물건의 가치는 24.5이고 3번째 물건의 1/4이 가방에 담긴 것을 확인할수 있다.

 

3. 탐욕 알고리즘의 한계

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

예

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

매 순간 최적의 선택을 하기때문에 탐욕 알고리즘은 한계가 있다. 매순간의 최적의 값이 전체 최적의 값과 다른 경우가 있을 수 있기 때문/ 근사치 추정에 활용