알고리즘 | 최적화 문제 | 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘

그리디 알고리즘의 기본 아이디어는 각 단계에서 현재의 상황에서 최적의 선택을 하는 것이다. 이러한 선택은 문제 해결에 있어서 전역적으로 최적이며, 각 단계에서의 선택은 이후 단계에 대한 선택을 제한하지 않는다.  

 

DP와 마찬가지로, 그리디 알고리즘은 일반적으로 최적화 문제를 해결하기 위해 사용된다. 또한, 그리디 알고리즘은 해를 찾기 위해 반복적인 선택을 해야 하는 문제에도 적용된다. 

 

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.
(...)
이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

(출처: 위키피디아)

 

핵심 개념

그리디 알고리즘의 대표적인 핵심 개념은 2가지: 1) 탐욕적 선택 조건, 2) 최적 부분 구조

지역 최적 선택(Local Optimal Choice) 라는 개념도 있지만 탐욕적 선택 조건과 거의 동일한 개념 같아서 일단은 패스

 

1. 탐욕적 선택 조건 (Greedy Choice Property):
   • 탐욕적 선택 조건은 전역 최적해를 찾기 위해 현재의 선택이 이후의 선택에 영향을 미치지 않음을 의미한다. 이 속성은 그리디 알고리즘의 핵심적인 부분이며, 각 단계에서의 선택이 독립적이어야 함을 나타낸다. 즉, 각 단계에서 최상의 선택을 하면서 이전 단계를 재고하지 않고 문제를 해결할 수 있다는 것을 의미한다.
   • 예시: 그래프에서 최소 신장 트리를 찾는 문제에서, 각 단계에서 최소 가중치의 간선을 선택하는 것이 탐욕적 선택 조건을 만족한다.
2. 최적 부분 구조 (Optimal Substructure):
   • DP와 마찬가지로, 그리디에서도 최적 부분 구조가 주요 조건이다. (문제를 분해 -> 부분 문제 해결 -> 전체 문제 해결)
   • 예시: 최단 경로 문제에서, 시작 정점에서 종단 정점까지의 최단 경로는 그 사이의 모든 중간 정점들에 대해 최단 경로로 구성되어 있어야 한다.

이 두가지 속성을 만족하지 않는다면 그리디 알고리즘을 적용하여 최적의 해를 구할 수 없다. 

 

 

구현방법

1. 기준 정의:
   • 그리디 알고리즘은 문제의 해결을 위해 각 단계에서 최적의 선택을 결정할 수 있는 기준을 필요로 한다.
   • 이 기준은 문제의 특성, 제약 조건, 그리고 목표에 따라 달라질 수 있다.
2. 최적의 선택:
   • 각 단계에서 기준에 따라 최적의 선택을 한다.
   • 이 선택은 현재의 정보만을 기반으로 하며, 미래의 결과를 예측하지 않는다.
3. 결과 확인 및 선택 수정:
   • 선택의 결과를 확인한다. 
   • 그리디 알고리즘은 일반적으로 이전의 선택을 수정하지 않지만, 문제의 특성에 따라 이전의 선택을 수정할 필요가 있을 수 있다.
4. 반복:
   • 문제의 조건이 충족될 때까지 위의 단계를 반복한다.
   • 이 과정에서 그리디 알고리즘은 각 단계에서 지역적으로 최적의 선택을 하며, 이러한 선택들이 전역적으로 최적의 해를 구성하게 된다.

 

위 내용을 배낭 문제(Knapsack Problem) 중 분할 가능한 배낭 문제(Fractional Knapsack Problem)를 기준으로 학습해보자.

 

배낭 문제(Knapsack Problem)는 주어진 무게 제한의 배낭과 일련의 물건들이 있을 때, 이 물건들의 가치의 합이 최대가 되도록 물건들을 배낭에 담는 문제이다. 각 물건은 무게와 가치를 가지며, 배낭의 무게 제한 내에서 물건들을 선택해야 한다. 이 중에 하나의 물건을 쪼갤 수 있으면 fractional 배낭 문제, 쪼갤 수 없고 넣거나 말거나의 선택이라면 0-1 배낭 문제이다. 

 

<도둑과 보석 상점 예시>

문제 상황:
예를 들어, 도둑이 보석 상점을 털었다고 가정합니다. 보석 상점에는 다양한 종류와 가치의 보석들이 있습니다. 도둑은 배낭에 보석들을 담아야 하며, 배낭은 무게 제한이 있습니다. 그러나 도둑은 보석을 잘게 쪼개서 담을 수 있습니다. 도둑은 배낭의 무게 제한 내에서 어떻게 보석을 담아야 가장 높은 가치의 보석을 훔칠 수 있을지 고민하게 됩니다.

예시:
보석들의 무게와 가치, 그리고 배낭의 무게 제한이 다음과 같다고 가정해봅니다:
- 보석 A: 무게 2kg, 가치 $3
- 보석 B: 무게 3kg, 가치 $4
- 보석 C: 무게 4kg, 가치 $5
- 배낭의 무게 제한: 5kg

입력 예시:
입력으로 물건들의 리스트와 배낭의 무게 제한이 주어집니다. 물건들의 리스트는 각 물건의 무게와 가치를 튜플로 묶어서 주어집니다. 
----------------------------
items = [(2, 3), (3, 4), (4, 5)] 
capacity = 5 
----------------------------

출력 예시:
출력으로 배낭에 담길 수 있는 물건들의 최대 가치를 반환합니다.
----------------------------
result = 7.0
----------------------------

 

 

도둑은 무게당 가치가 높은 보석부터 배낭에 담아야 한다.

무게당 가치를 계산하면, 보석 A는 1.5($3/2kg$), 보석 B는 약 1.33($4/3kg$), 보석 C는 1.25($5/4kg$)이 된다. 따라서 도둑은 배낭에 남은 용량이 0kg이 될 때까지 보석 A -> 보석 B -> 보석 C 순으로 배낭에 담는다.

 

def fractional_knapsack(items, capacity):
    # Step 1: 기준 정의
    # 무게당 가치를 계산하여 물건들을 정렬
    # 무게당 가치가 높은 물건부터 선택하는 것이 기준이 된다. 
    items.sort(key=lambda item: item[1]/item[0], reverse=True)
    
    total_value = 0  # 배낭의 총 가치
    for item in items:
        weight, value = item
        
        # Step 2: 최적의 선택
        # 무게 제한 내에서 무게당 가치가 가장 높은 물건부터 선택하여 배낭에 넣는다. 
        if capacity >= weight:
            capacity -= weight  # 배낭의 남은 무게 업데이트
            total_value += value  # 배낭의 총 가치 업데이트
        else:
            # 무게 제한이 남아 있지만 물건을 완전히 담을 수 없는 경우,
            # 물건을 분할하여 배낭에 넣는다. 
            fraction = capacity / weight  # 분할 비율 계산
            total_value += value * fraction  # 분할된 물건의 가치를 총 가치에 추가
            break  # 배낭의 무게 제한에 도달했으므로 종료
        
    
    return total_value  # 배낭의 총 가치 반환

### 입력 및 출력 부분 ###
items = [(2, 3), (3, 4), (4, 5)]
capacity = 5

result = fractional_knapsack(items, capacity)
print(result)  # 7.0

 

 

해당 문제에서는 step3. 수정 작업이 필요하지 않다.