탐욕 알고리즘(Greedy Algorithm)의 한계와 극복 방법에 대해 알아보자.
탐욕 알고리즘(Greedy Algorithm)은 각 단계에서 가장 최적인 선택을 함으로써 전체 문제의 최적해를 찾고자 하는 기법이다. 단순한 구조와 빠른 실행 속도로 인해 다양한 문제에서 활용되지만, 항상 최적해를 보장하지 않는다는 한계도 존재한다. 이번 글에서는 탐욕 알고리즘이 실패하는 경우와 이를 극복하기 위한 방법에 대해 살펴보겠다.
1. 탐욕 알고리즘의 개념과 장점
(1) 탐욕 알고리즘이란?
탐욕 알고리즘은 문제를 해결하는 과정에서 각 단계에서 최선이라고 판단되는 선택을 연속적으로 수행하여 전체 문제의 해결을 시도하는 방법이다. 이 과정에서 한 번 선택한 해는 되돌릴 수 없으며, 전체적인 최적해를 보장하지 않을 수도 있다.
(2) 탐욕 알고리즘의 대표적인 활용 사례
탐욕 알고리즘은 다양한 문제에서 활용되며, 대표적인 예는 다음과 같다:
최소 신장 트리(Minimum Spanning Tree): 크루스칼(Kruskal) 및 프림(Prim) 알고리즘
최단 경로 문제(Shortest Path Problem): 다익스트라(Dijkstra) 알고리즘
활동 선택 문제(Activity Selection Problem): 최대한 많은 활동을 선택하는 문제
동전 거스름돈 문제(Coin Change Problem): 최소한의 동전으로 특정 금액을 만드는 문제
(3) 탐욕 알고리즘의 장점
빠른 실행 속도: 동적 계획법(Dynamic Programming)이나 분할 정복(Divide and Conquer) 방식보다 계산 속도가 빠름
단순한 구현: 문제를 작은 단위로 나누어 처리하기 때문에 직관적이며 구현이 용이함
일부 문제에서는 최적해 보장: 특정 조건을 만족하는 경우(예: 최적 부분 구조와 탐욕적 선택 속성) 최적해를 구할 수 있음
2. 탐욕 알고리즘이 실패하는 경우
(1) 최적 부분 구조 조건이 성립하지 않는 경우
탐욕 알고리즘이 올바르게 동작하려면 최적 부분 구조(Optimal Substructure)가 성립해야 한다. 즉, 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 한다. 하지만 일부 문제에서는 전체적인 최적해가 각 단계에서의 최적해를 단순히 조합한 결과와 다를 수 있다.
예제: 배낭 문제(Knapsack Problem)
배낭 문제에서 탐욕 알고리즘을 사용하면 가치 대비 무게 비율이 높은 물건부터 선택하는 방식이 일반적이다. 그러나 이 방식은 항상 최적해를 보장하지 않는다. 예를 들어, 다음과 같은 물건이 있을 때:
물건 A: 무게 3kg, 가치 60
물건 B: 무게 2kg, 가치 100
물건 C: 무게 4kg, 가치 120
배낭의 용량이 5kg이라면, 가치 대비 무게 비율이 가장 높은 물건 B(100/2 = 50)를 먼저 선택하고 남은 용량에 대해 물건 A(60/3 = 20)를 선택할 것이다. 그러나 실제 최적해는 물건 C(120)를 선택하는 것이다.
(2) 탐욕적 선택 속성이 성립하지 않는 경우
탐욕 알고리즘이 성공하려면 탐욕적 선택 속성(Greedy Choice Property)이 만족되어야 한다. 즉, 현재 단계에서 최선의 선택을 하는 것이 이후 단계에서도 최적해로 이어져야 한다. 하지만 일부 문제에서는 이러한 속성이 성립하지 않아 최적해를 놓칠 수 있다.
예제: 동전 거스름돈 문제 (Greedy Coin Change Problem)
동전의 종류가 {1, 3, 4}일 때, 6원을 거슬러 주는 경우를 생각해보자. 탐욕 알고리즘은 가장 큰 동전(4)을 먼저 선택한 후, 나머지 2원을 위해 동전 1을 두 개 선택할 것이다. 하지만 최적해는 동전 3을 두 개 선택하는 것이다.
(3) 지역 최적해(Local Optimum)와 전역 최적해(Global Optimum)의 차이
탐욕 알고리즘은 매 단계에서 지역 최적해(Local Optimum)를 선택하지만, 전체 문제의 전역 최적해(Global Optimum)에 도달하지 못할 수도 있다.
예제: 최장 증가 부분 수열(Longest Increasing Subsequence)
주어진 숫자 배열에서 가장 긴 증가하는 부분 수열을 찾는 문제를 탐욕적으로 해결하려 하면, 항상 현재 숫자보다 큰 숫자만 선택하는 방식이 될 수 있다. 하지만 전체적인 최적해를 구하기 위해서는 이전에 선택한 값을 수정해야 할 수도 있다.
3. 탐욕 알고리즘의 한계를 극복하는 방법
(1) 동적 계획법(Dynamic Programming)과의 조합
탐욕 알고리즘이 실패하는 많은 문제는 동적 계획법(DP)을 통해 해결할 수 있다. DP는 중복된 부분 문제를 저장하고 활용함으로써 탐욕 알고리즘의 한계를 극복한다.
예제: 0/1 배낭 문제 해결
0/1 배낭 문제는 탐욕 알고리즘으로 해결하기 어렵지만, 동적 계획법을 사용하면 최적해를 찾을 수 있다. 이때 DP 테이블을 활용하여 무게와 가치를 비교하면서 최적의 조합을 선택한다.
(2) 분할 정복(Divide and Conquer) 기법 사용
탐욕 알고리즘이 최적해를 보장하지 못하는 경우, 문제를 더 작은 부분으로 나누어 해결하는 분할 정복 기법이 유용할 수 있다.
예제: 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)
정렬 문제에서는 탐욕적인 선택이 항상 최적해를 보장하지 않기 때문에, 병합 정렬과 같은 분할 정복 기법이 더욱 안정적이다.
(3) 후퇴 추적(Backtracking)과 탐욕 알고리즘의 조합
경우의 수를 모두 고려해야 하는 문제에서는 탐욕 알고리즘 대신 후퇴 추적(백트래킹) 기법을 사용할 수 있다.
예제: 외판원 문제(Travelling Salesman Problem, TSP)
탐욕 알고리즘을 사용하면 항상 가장 가까운 도시를 방문하는 방식이지만, 최적해를 보장하지 못한다. 이를 해결하기 위해 분기 한정(Branch and Bound) 기법을 활용하여 전체 탐색을 수행할 수 있다.
탐욕 알고리즘은 빠르고 간단한 해결책을 제공하지만, 항상 최적해를 보장하지는 않는다. 최적 부분 구조와 탐욕적 선택 속성이 만족되지 않는 문제에서는 동적 계획법, 분할 정복, 백트래킹 등의 기법을 활용하여 보다 정확한 해를 찾을 수 있다. 따라서 문제의 특성을 잘 분석하고, 적절한 알고리즘을 선택하는 것이 중요하다.