[파이썬 | 알고리즘] 탐욕 알고리즘(Greedy algorithm)

지난번에는 깊이 우선 탐색(Depth-First Search)에 대해 알아보았습니다.

이번에는 탐욕 알고리즘(Greedy algorithm)에 대해 알아보겠습니다.

 

탐욕 알고리즘(Greedy algorithm)

탐욕 알고리즘이란 최적의 해에 가까운 값을 구하기 위해

사용되는 알고리즘이다. 여러 경우 중 하나를 결정해야할 때마다,

매순간 최적이라 생각되는 경우를 선택하는 방식으로 최종값을 구한다.

 

탐욕 알고리즘(Greedy algorithm)의 예

문제 : 동전 문제

●지불해야 하는 값이 5872원 일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불해라.

 

접근법: 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 접근

coin_list = [1, 100, 50, 500] #coin_list에 가지고있는 동전 종류를 넣는다.
print (coin_list)
coin_list.sort(reverse=True)  #coin_list를 큰 값이 앞으로 오도록 접근시킨다.
print (coin_list)

coin_list 출력

coin_list = [1, 50, 100, 500]      #coin_list는 동전 종류

def min_coin_count(value, coin_list):    #value는 지불해야 하는 값, coin_list는 동전 종류
    total_coin_count = 0                 #토탈 코인의 수 0개   
    details = list()                     #동전 종류와 개수를 담을 리스트
    coin_list.sort(reverse=True)         #coin_list를 큰 값이 앞으로 오도록 정렬
    for coin in coin_list:               #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(5872, coin_list)

동전 문제 코드 테스트 결과

 

문제 : 부분 배낭 문제 (Fractional Knapsack Probleml)

●무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣어라.

   - 각 물건은 무게(w)와 가치(v)로 표현될 수 있음

   - 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음

물건(i)	물건1	물건2	물건3	물건4	물건5
무게(w)	10	15	20	25	30
가치(v)	10	7	8	15	17

 

data_list = [(10, 10), (15, 7), (20, 8), (25, 15), (30, 17)]

def get_max_value(data_list, capacity): #data_list는 물건 당 무게, 가치 /capacity 배낭의 용량
    data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True) 
    ##무게 대비 가치가 큰 순으로 차례대로 정렬
    total_value = 0 #배낭의 가치
    details = list()#물건의 무게와 가치 개수를 담을 세부 리스트
    
    for data in data_list:                               #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]                #fraction은현재 물건의 무게 분의 배낭의 용량
            total_value += data[1] * fraction            #배낭의 가치에 현재 물건의 가치 * fraction 추가
            details.append([data[0], data[1], fraction]) #세부리스트에 현재 물건의 무게와 가치. 물건의 개수(fraction) 추가
            break
    return total_value, details                          #배낭의 가치, 세부리스트 리턴

get_max_value(data_list, 50) #배낭의 용량이 50인 부분 배낭 문제

부분 배낭 문제 코드 테스트 결과

테스트 결과

 

탐욕 알고리즘 구현 코드가 정상적으로 구현됨

이상으로 [파이썬 | 알고리즘] 탐욕 알고리즘에 대해 알아보았습니다,