그리디(Greedy) 알고리즘이란?
Greedy 알고리즘은 각 단계에서 가장 최선의 선택을 하는 방식으로 문제의 최적해를 찾아가는 알고리즘입니다. 이는 동적 프로그래밍(Dynamic Programming)이 일부 간단한 문제에 대해 비효율적일 수 있다는 점에서 착안되었습니다.
하지만 그리디 알고리즘이 항상 최적해를 보장하는 것은 아니며, 특정 조건을 만족하는 문제에만 적용할 수 있습니다.
그리디 알고리즘 적용 조건
그리디 알고리즘을 사용하기 위해서는 다음 두 가지 조건을 만족해야 합니다.
-
탐욕적 선택 속성 (Greedy Choice Property)
- 각 단계에서 하는 탐욕적인 선택이 최종적인 최적해를 구하는 데 영향을 주지 않아야 합니다. 즉, 부분적인 최적해가 전체 문제의 최적해로 이어져야 합니다.
-
최적 부분 구조 (Optimal Substructure)
- 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 합니다. 이는 동적 프로그래밍과 공통되는 특징이기도 합니다.
결론적으로, 그리디 알고리즘은 각 선택이 독립적이며, 현재의 최적 선택이 전체의 최적해로 이어지는 문제에 효과적입니다.