[알고리즘] 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘은 현재 단계에서 가장 최선의 선택을 반복적으로 수행하여 전체 문제의 최적 해를 구하려는 방법론이다. 선택할 때마다 가장 좋다고 생각되는 것을 선택하며 최종적인 해답을 구하는 알고리즘이다. 그렇기 때문에 문제를 해결하는 과정을 단순화하고 빠르게 수행한다.

 

주요 개념

1. 단계별 최적 선택(Local Optimal Choice):
   • 탐욕 알고리즘은 문제를 해결할 때, 매 단계에서 가능한 선택지 중 가장 최선의 선택을 즉시 합니다. 이 선택은 전체 문제의 최종 해답에 영향을 미치지만, 그 순간의 최선만을 고려하고 미래에 대한 고려는 하지 않습니다.
2. 최적해 보장 조건(Optimal Substructure):
   • 탐욕 알고리즘은 모든 부분 문제에서의 최선의 선택이 전체 문제에서도 최선의 선택이 될 때 효과적입니다. 즉, 탐욕 알고리즘이 문제를 성공적으로 해결하려면 부분 문제에서의 최적해가 전체 문제의 최적해로 이어지는 특성을 가져야 합니다. 이를 **최적 부분 구조(Optimal Substructure)**라고 합니다.
3. 탐욕 선택 속성(Greedy Choice Property):
   • 탐욕 알고리즘은 탐욕적 선택을 반복하는 구조로 이루어져 있으며, 각 선택이 문제의 최종 해를 구하는 과정에서 해를 손상시키지 않는다는 성질이 있습니다. 매 순간 가장 좋아 보이는 것을 선택해도 전체 해답이 잘못되지 않는 특성을 이용합니다.

 

탐욕 알고리즘의 예시

1. 거스름돈 문제:

• 문제: 1000원을 내고 430원의 물건을 샀을 때, 가장 적은 동전으로 거스름돈 570원을 주는 방법은?
• 알고리즘: 500원 동전을 먼저 주고, 나머지 70원은 50원 동전 하나와 10원 동전 두 개를 줍니다.
  • 탐욕적인 선택: 매번 가장 큰 단위의 동전부터 주는 방식입니다. 여기서는 500원이 가장 큰 동전이므로 이를 먼저 선택합니다.
  • 최적해: 탐욕적으로 선택한 결과가 최적의 해답이 됩니다.

2. 최소 신장 트리(Minimum Spanning Tree):

• 문제: 연결된 그래프에서 모든 노드를 포함하는 최소 비용의 트리를 찾는 문제.
• 알고리즘: 크루스칼(Kruskal) 또는 프림(Prim) 알고리즘이 대표적인 탐욕 알고리즘입니다. 매 단계에서 가장 가중치가 작은 간선을 선택하고, 이를 반복하여 최소 신장 트리를 구성합니다.

3. 활동 선택 문제(Activity Selection Problem):

• 문제: 주어진 여러 활동이 서로 겹치지 않도록 가장 많은 활동을 선택하는 문제.
• 알고리즘: 가장 빨리 끝나는 활동부터 선택하는 것이 탐욕적인 방법입니다. 먼저 끝나는 활동을 선택하면, 이후 더 많은 활동을 할 수 있기 때문입니다.
  • 예를 들어, 활동 A(1-3시)와 활동 B(2-5시)가 있다면, 탐욕적 선택은 더 빨리 끝나는 활동 A를 선택합니다.

 

탐욕 알고리즘의 장점

• 단순성: 구현이 매우 간단하고 직관적입니다. 문제를 해결하는 데 있어 복잡한 계산이 필요 없으며, 매 단계에서 최선의 선택을 바로바로 할 수 있습니다.
• 빠른 속도: 일반적으로 탐욕 알고리즘은 다른 복잡한 알고리즘보다 더 빠르게 작동합니다. 대부분의 탐욕 알고리즘은 시간 복잡도가 O(n) 또는 O(nlog⁡n)로 효율적입니다.

탐욕 알고리즘의 단점

• 최적해 보장 불가: 탐욕 알고리즘은 항상 최적의 해를 보장하지는 않습니다. 부분 문제에서 최적의 선택을 하더라도, 전체 문제에서 그 선택이 최선이 아닐 수 있습니다. 일부 문제는 탐욕적 접근이 적합하지 않으며, 더 정교한 알고리즘(예: 동적 계획법, 백트래킹)이 필요합니다.
• 탐욕 선택이 전체 문제의 최적해로 이어지지 않을 수 있음: 매 순간 최선의 선택이 최종적으로는 잘못된 결과를 낼 수 있습니다. 예를 들어, 일부 배낭 문제(knapsack problem)에서는 탐욕적 접근이 잘못된 해를 도출할 수 있습니다.

 

탐욕 알고리즘의 응용 분야

• 그래프 이론: 최소 신장 트리(MST), 최단 경로 문제(Dijkstra 알고리즘) 등.
• 자원 배분: 활동 선택 문제, 배낭 문제 등에서 자원을 최적으로 배분하는 데 사용됩니다.
• 문자열 압축: 허프만 코딩(Huffman Coding)을 통해 데이터 압축에 활용됩니다.
• 일정 관리: 겹치지 않는 최대 활동을 선택하거나, 일정의 최적화를 위해 사용됩니다.