탐욕 알고리즘 - Greedy

탐욕 알고리즘

• 매순간 최적의 해를 선택하는 방식
• 근사치 추정에 활용 (반드시 최적의 해를 구할 수 있는 것은 아니다.)

동전 문제

coin_list = [10, 50, 100, 500]
def min_coin_count(money, coin_list):
    quotient_list = []
    coin_list.sort(reverse=True)
    answer = 0
    for coin in coin_list:
        count = 0
        quotient = money // coin
        money = money % coin
        count += quotient
        answer += count
        quotient_list.append([coin, count])
    return answer,quotient_list

몫은 quotient, list 내림차순은 sort(reverse=True)

부분 배낭 문제

• 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
• 물건의 일부를 쪼개서 배낭에 넣을 수 있다. Fractional Knapsnack Problem

def get_max_value(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:
        if capacity >= data[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

가치 / 무게를 통해 우선으로 넣을 공간 선택, lambda를 사용하여 내림차순 정렬

탐욕 알고리즘의 한계

• 반드시 최적의 해를 구할 수 있는 것은 아니다.
• 트리 구조라고 가정하고, 탐욕알고리즘 시행 시 자식 노드까지의 경우의수만 고려 (최적이 아닐 수 있다.)