탐욕 알고리즘 Greedy 정당성 증명과 최적 부분 구조
우리는 매 순간 최선의 선택을 하며 살아갑니다. 하지만 오늘의 최선이 내일의 불행을 초래할 수 있듯이, 알고리즘의 세계에서도 당장 눈앞의 이득만을 쫓는 방식은 위험할 수 있습니다. 탐욕 알고리즘(Greedy Algorithm)은 미래를 고려하지 않고 현재 시점에서 가장 최선이라고 판단되는 해답을 선택하는 기법입니다. 구현이 매우 간단하고 속도가 빠르다는 강력한 장점이 있지만, 전역적인 최적해(Global Optimum)를 보장하지 못한다는 치명적인 함정이 존재합니다. 본 포스팅에서는 그리디 알고리즘이 성립하기 위한 엄격한 조건과, 이를 수학적으로 증명하는 매커니즘을 상세히 분석해 보겠습니다.
1. 탐욕 알고리즘의 본질: 지역 최적해의 선택
그리디 알고리즘의 핵심 철학은 '선택의 순간마다 최적의 해를 구한다'는 것입니다. 이는 복잡한 계산을 생략하고 직관적인 결정을 내릴 수 있게 해주지만, 탐욕적 선택이 모여 전체의 최적을 이룰 수 있는지는 별개의 문제입니다. 그리디가 유효하게 작동하려면 문제 자체가 특정한 구조적 특징을 가지고 있어야 합니다. 만약 이를 무시하고 그리디를 적용한다면, 부분적으로는 최선일지 몰라도 전체적으로는 매우 비효율적인 결과를 얻게 되는 '그리디의 함정'에 빠지게 됩니다.
1-1. 그리디 알고리즘의 성립 조건: 두 가지 기둥
어떤 문제에 그리디를 적용할 수 있는지 판단하는 기준은 크게 두 가지로 나뉩니다. 이 두 조건이 동시에 충족될 때만 그리디는 비로소 정당성을 얻습니다.
- 탐욕적 선택 속성(Greedy Choice Property): 이전의 선택이 이후의 선택에 영향을 주지 않으며, 현재의 최선이 결국 전체 최적해의 일부분이 된다는 성질입니다.
- 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 최적해 구성 요소들이 그 하위 문제들의 최적해들로 이루어져 있어야 한다는 원칙입니다.
2. 최적 부분 구조(Optimal Substructure)의 심층 분석
최적 부분 구조는 동적 계획법(DP)에서도 중요하게 다루어지는 개념입니다. 하지만 그리디에서의 최적 부분 구조는 조금 더 엄격한 의미를 가집니다. 전체 문제의 해결책이 부분 문제의 해결책들로부터 효율적으로 도달할 수 있어야 하며, 부분 문제를 해결하는 과정에서 선택된 탐욕적인 해가 전체의 흐름을 방해해서는 안 됩니다. 예를 들어 최단 경로를 찾는 다익스트라 알고리즘은 현재의 최단 거리를 확정 짓는 것이 전체 최단 경로의 구성 요소가 되므로 최적 부분 구조를 완벽히 만족합니다.
3. 그리디의 함정과 반례(Counter-example)
그리디 알고리즘이 실패하는 가장 대표적인 사례는 앞서 다룬 0-1 배낭 문제(Knapsack Problem)입니다. 가성비가 가장 좋은 물건부터 담는 그리디 전략을 취할 경우, 무게 제한 때문에 더 가치 있는 물건의 조합을 놓치게 되는 상황이 발생합니다. 또한 거스름돈 문제에서도 동전 단위가 서로 배수 관계가 아니라면(예: 500원, 400원, 100원 조합으로 800원을 거슬러 줄 때), 그리디는 500원+100원+100원+100원(4개)을 제시하지만 최적해는 400원+400원(2개)입니다. 이처럼 단위 간의 논리적 연계성이 부족할 때 그리디는 무력해집니다.
4. 알고리즘의 정당성을 증명하는 방법
실제 코딩 테스트나 알고리즘 설계 과정에서 내가 세운 그리디 전략이 맞는지 확인하려면 두 가지 증명 기법을 주로 사용합니다.
4-1. 수학적 귀납법(Mathematical Induction)
첫 번째 단계에서의 탐욕적 선택이 최적해의 일부임을 증명하고, $n$번째 단계까지의 선택이 최적일 때 $n+1$번째 단계에서도 최적해를 구성함을 보여주는 방식입니다.
4-2. 모순 증명법(Proof by Contradiction)
우리가 선택한 탐욕적인 해보다 더 좋은 해가 존재한다고 가정했을 때, 그것이 논리적으로 불가능함을 입증하는 방식입니다. 혹은 어떤 임의의 최적해가 있을 때, 그 해의 일부분을 우리의 탐욕적 선택으로 교체(Exchange Argument)해도 결과가 나빠지지 않음을 증명함으로써 정당성을 확보합니다.
1. 원리: 현재 단계에서의 국소적 최적해를 선택하여 전역 최적해에 도달하려는 시도입니다.
2. 조건: 탐욕적 선택 속성과 최적 부분 구조가 보장되어야만 수학적 정당성을 가집니다.
3. 주의: 증명 없이 사용하면 오답의 위험이 크므로, 항상 반례를 고민하고 교체 증명법을 활용해야 합니다.