그리디 알고리즘
그리디 알고리즘 (Greedy Algorithm)
그리디 알고리즘(Greedy Algorithm, 탐욕법)은 각 단계에서 그 순간 가장 좋다고 생각되는 선택(locally optimal choice)을 반복적으로 수행함으로써, 최종적으로 전체 문제의 최적해(global optimum)를 구하고자 하는 알고리즘 설계 기법입니다. 미래를 고려하지 않고 현재의 선택에만 집중하는 방식이 '탐욕적'이라고 하여 이러한 이름이 붙었습니다.
🎯 그리디 알고리즘의 적용 조건
그리디 알고리즘은 모든 문제에 적용할 수 없으며, 아래의 두 가지 조건이 만족될 때 최적해를 보장합니다.
- 탐욕적 선택 속성 (Greedy Choice Property)
> * '정의': 앞의 선택이 이후의 선택에 영향을 주지 않으며, 각 단계에서 한 국소적인 최적해가 전체 문제의 최적해로 이어지는 속성입니다. 즉, 지금의 최적 선택이 나중에 후회를 만들지 않아야 합니다.
- 최적 부분 구조 (Optimal Substructure)
> * '정의': 문제의 최적해가 그 부분 문제들의 최적해를 포함하는 구조입니다. (이 조건은 동적 계획법과 공통됩니다.)
- 정당성 증명 : 그리디 알고리즘을 문제 해결에 사용하기 위해서는, '매 순간의 최적해가 결국 전체 문제의 최적해'라는 것을 반드시 수학적으로 증명해야 합니다. 이 증명 과정이 없는 그리디 알고리즘은 단지 어림짐작(heuristic)에 불과합니다.
💡 개발자 핵심 Point
- 동적 계획법(Dynamic Programming)과의 차이
> * 그리디 : 매 순간의 선택이 최적이므로, 한 번 선택하면 다시 고려하지 않습니다. 문제를 부분 문제로 나누지 않고, 순차적으로 최적의 선택을 쌓아갑니다. > * DP : 모든 가능한 선택지를 고려하고, 부분 문제들의 최적해를 바탕으로 전체 최적해를 구합니다. 따라서 그리디보다 일반적으로 느릴 수 있습니다.
- 대표적인 그리디 알고리즘 문제
> * 거스름돈 문제 : 가장 큰 단위의 화폐부터 차례대로 거슬러 주는 문제. (단, 화폐 단위가 특정 조건을 만족해야 함) > * 최소 신장 트리 (MST) > > * 크루스칼 알고리즘 : 가장 가중치가 작은 간선부터 차례대로 추가하되, 사이클을 만들지 않는 간선만 선택합니다. > > * 프림 알고리즘 : 시작 정점에서부터, 현재 트리에 연결된 간선 중 가장 가중치가 작은 것을 선택하여 트리를 확장합니다. > * 최단 경로 알고리즘 > > * 다익스트라 알고리즘 : 현재까지의 최단 경로가 확정된 정점들로부터, 가장 가까운 다음 정점을 선택합니다. > * 활동 선택 문제 (Activity Selection Problem) : 종료 시간이 가장 빠른 활동부터 선택하여, 가장 많은 활동을 선택하는 문제입니다.
