그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘 개요

그리디 알고리즘(greedy algorithm)은 각 단계에서 현재 상황에서의 최적의 선택을 함으로써 문제에 대한 최적화된 해결책을 찾는 알고리즘의 일종이다. 다시 말해  각 단계에서 이루어지는 선택이 가능한 최선의 해결책으로 이어지기를 바라며(욕망하며) 각 단계에서 사용 가능한 최선의 옵션을 선택하는 것이다.

그리디 알고리즘은 컴퓨터 과학, 운영 연구 및 경제학의 문제를 포함하여 최적화가 필요한 문제상황을 해결하는 데 사용될 수 있다. 

 

사용 예시

• 최소신장트리(Minimum spanning tree problem)
• 허프만 코드(Huffman coding problem)
• 다익스트라 알고리즘(Dijkstra algorithm
•  
• 활동 선택 문제(Activity selection problem)
• 배낭 채우기(Knapsack problem)

예시

아래는 배낭 채우기 문제에 대한 파이썬 코드입니다. 

배낭 채우기 문제는 일정 가치(value)와 무게(weight)가 있을 때 배낭에 최대한 가치가 높도록 짐을 고르는 방법을 찾는 문제입니다.

def knapsack(value, weight, max_w):  # (가치, 무게, 가방용량)
    # 각 항목의 단위 중량에 대한 값 계산
    value_per_unit = [(v/w, w) for v, w in zip(value, weight)]
    # 내림차순 정렬
    value_per_unit.sort(reverse=True)
    total_value = 0
    for vpw, w in value_per_unit:
        if max_w == 0:
            break
        # 가능한 많이 가지기
        take = min(w, max_w)
        # 총 가치와 용량
        total_value += take * vpw
        max_w -= take
    return total_value

이 코드의 knapsack 함수는 '항목의 가치', '가중치(무게)', 가방의 최대 용량을 인자로 받습니다. 

먼저 각 항목에 대해 단위 무게당 값을 계산하여 무게당 값이 감소하는 순서로 정렬합니다. 

그리고 순서대로 항목을 반복하여 배낭이 가득 찰 때까지 최대한 많은 항목을 넣습니다. 

그리고 배낭에 담긴 총 가치를 반환합니다.