그리디 알고리즘(Greedy Algorithm)
그리디 알고리즘은 문제를 해결할 때, 매 단계에서 최선의 선택을 하는 알고리즘입니다. 이 알고리즘은 전체 문제를 해결하기 위한 국소 최적화(local optimum)를 선택하며, 이를 통해 전체 문제의 전역 최적화(global optimum)를 달성한다고 가정합니다. 그리디 알고리즘은 일반적으로 탐욕적인 선택이 항상 최적의 해결책으로 이어지는 문제에 적합합니다.
그리디 알고리즘의 특징
1. 현재 상황에서 최적이라고 생각되는 선택을 한다: 그때그때 가장 좋은 선택을 하기 때문에 미래를 고려하지 않습니다.
2. 문제를 해결할 수 있는 "단계적" 접근 방식을 사용합니다.
3. 그리디 알고리즘이 항상 최적해를 보장하는 것은 아니므로, 이 알고리즘을 적용할 수 있는 문제에 적합한지 먼저 검토해야 합니다.
그리디 알고리즘의 적용 예시
1. 동전 교환 문제: 주어진 금액을 최소 개수의 동전으로 교환하는 문제 (그리디 알고리즘이 잘 작동함)
2. 활동 선택 문제: 주어진 활동 중, 겹치지 않게 최대 활동을 선택하는 문제
3. 프림 알고리즘/크루스칼 알고리즘: 최소 신장 트리(MST)를 찾는 알고리즘
4. 허프만 코드: 압축 알고리즘에서 사용하는 트리 구조 생성
그리디 알고리즘이 잘 적용되는 조건
1. 문제가 "부분 최적성"을 가질 때: 즉, 부분 문제에서의 최적 선택이 전체 최적 선택으로 이어지는 경우.
2. 그리디 선택 속성이 만족될 때: 각 단계에서의 선택이 전체 해를 구성할 때 최적이 되는 성질이 있을 때.
그리디 알고리즘의 한계
- 그리디 알고리즘은 모든 문제에서 최적해를 보장하지 않습니다. 예를 들어, 일부 동전 교환 문제에서는 그리디 방법이 최적해를 찾지 못할 수 있습니다. (예: 동전 종류가 {1, 3, 4}일 때, 6을 교환하는 경우)
따라서 문제에 따라 그리디 알고리즘이 최적해를 제공할 수 있는지 판단이 필요합니다.