[그리디] 개념 정리 및 활용 사례 (Feat. 최소 신장 트리 & 배낭 문제)

그리디 개념

그리디는 '탐욕스러운'이라는 영단어 뜻처럼, 문제 해결 과정에서 결정하는 순간마다 눈 앞에 보이는 최선의 선택을 하는 알고리즘을 말합니다. 이러한 특성으로 인해 '지역 최적해를 추구한다'고 생각할 수 있습니다. 그리디 알고리즘은 부분적으로는 최적해, 전체적으로는 최선의 해를 구합니다.

 

그리디 알고리즘은 아래 2가지와 같은 특정 상황에서 최적해를 보장합니다. 

 

1. 최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치

2. 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 주지 않음

 

위 조건을 만족하는 경우, 최적해를 도출하지만,

조건을 만족하지 않는 경우, 현재의 최적의 결정이 이후 선택에 제약이 될 수 있으므로,

항상 최적해를 도출하지 못한다는 한계가 있습니다. 

 

그리디 알고리즘 활용 사례

그리디 알고리즘을 쓰면 좋은 상황에 대해 알아봅시다. 

 

최소 신장 트리(MST)

최소 신장 트리는 그리디 알고리즘을 사용하는 대표적인 트리 형태의 자료구조입니다. 신장 트리는 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프를 말합니다. 최소 신장 트리(MST, Minimum Spanning Tree)란, 신장 트리 중 간선 가중치 합이 최소인 것을 말합니다. MST는 네트워크 또는 항공기 운항 경로를 최적화할 때 활용된다고 합니다. 

 

최소 신장 트리를 구하는 대표적인 그리디 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 있습니다.

 

1. 프림 알고리즘 : 임의 정점을 하나 선택해서 MST에 추가 → MST와 연결된 정점 중 가장 적은 간선 가중치로 연결할 수 있는 정점(순환을 형성하지 않아야 함)을 MST에 추가 (그리디적 선택) → 신장 트리 조건을 만족할 때까지 반복 

 

2. 크루스칼 알고리즘 : 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬 → 가중치가 낮은 간선(순환을 형성하지 않아야 함)부터 MST에 하나씩 추가 (그리디적 선택) → 신장 트리 조건을 만족할 때까지 반복

 

배낭 문제

무게와 가치가 다른 짐을 조합해서 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제를 말합니다. 목표는 '최대한 배낭에 높은 가치의 짐을 넣는다'이지만 짐을 쪼갤 수 있는지 여부에 따라 부분 배낭 문제와 0/1 배낭 문제로 나뉩니다. 

 

1. 짐을 쪼갤 수 있다 → 부분 배낭 문제  (그리디 알고리즘 적용 O)

• 짐별로 무게당 가치를 구함
• 무게 당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣음
  • '배낭 용량 > 짐 무게'인 경우, 짐을 쪼개 넣음
• 배낭이 다 찰 때까지 반복

이 경우, 매 순간 짐을 선택하는 방식이 무게당 가치가 높은 짐이므로, 최적 부분 구조를 만족합니다. 짐을 쪼갤 수 있기 때문에, 앞에서 선택한 짐이 다른 짐 선택에 영향을 주지 않으므로, 그리디적 선택 요소도 만족합니다. 따라서, 최적해를 보장합니다.

 

2. 짐을 쪼갤 수 없다 → 0/1 배낭 문제 (그리디 알고리즘 적용 X)

현재의 짐 선택이 다음 짐 선택에 영향을 주기 때문에, 그리디 알고리즘으로는 최적해를 구할 수 없습니다. 최적해를 구하려면, 동적계획법으로 접근해야 합니다. 

 

그리디 알고리즘을 이용한 문제 해결

거스름돈 주기

  

    
    
    
    
  
"""
[거스름돈 주기]
당신은 상점에서 계산을 마치고 거스름돈을 돌려받아야 합니다.
다만 거스름돈을 최소한의 화폐수로 받고 싶어졌습니다.
거스름돈 amount가 있을 때 화폐 단위 [1,10,50,100]을 최소한으로
사용한 화폐 리스트를 반환하는 함수를 반환하세요.
"""

def solution(amount):
    denominations = [100,50,10,1]
    change = []
    for coin in denominations:
        # 현재 화폐 단위로 최대한 거슬러 줄 수 있는 동전의 개수를 구함
        count = amount // coin
        change.extend([coin]*count)
        # 정산이 완료된 거스름돈을 제외함
        amount %= coin
    return change
    

# test case 1 - [100,10,10,1,1,1]
amount = 123

# test case 2 - [100,100,100,50]
amount = 350

print(solution(amount))

 

 

부분 배낭 문제

  

    
    
    
    
  
"""
[부분 배낭 문제]
무게와 가치가 있는 짐 items와 배낭 weight_limit이 주어질 때,
부분 배낭 문제 (짐을 쪼갤 수 있음)를 푸는 함수를 작성하세요.
"""

# 각 물건의 단위 무게당 가치를 계산하여 items 리스트에 추가
def calculate_unit_value(items):
    for item in items:
        item.append(item[1]/item[0])
    return items


# 단위 무게당 가치가 높은 순으로 물건을 정렬
def sort_by_unit_value(items):
    items.sort(key=lambda x: x[2], reverse=True)
    return items


def knapsack(items, weight_limit):
    total_value = 0  # 선택한 물건들의 총 가치를 저장하는 변수
    remaining_weight = weight_limit  # 남은 무게의 한도를 저장하는 변수

    for item in items:
        if item[0] <= remaining_weight:
            # 물건을 통째로 선택
            total_value += item[1]
            remaining_weight -= item[0]
        else:
            # 남은 무게 한도가 물건의 무게보다 작으면 쪼개서 일부분만 선택
            fraction = remaining_weight / item[0]
            total_value += item[1] * fraction
            break
    return total_value


def solution(items, weight_limit):
    items = calculate_unit_value(items)
    items = sort_by_unit_value(items)
    return round(knapsack(items, weight_limit),2)
    

# test case 1 - 27.33
items = [[10,19],[7,10],[6,10]]
weight_limit = 15

# test case 2 - 240
items = [[10,60],[20,100],[30,120]]
weight_limit = 50

print(solution(items, weight_limit))