그리디 알고리즘(Greedy Algorithm)은 최적화 문제를 해결하는 알고리즘으로, 각 단계마다 가장 최선의 선택을 하는 방식으로 동작합니다.
이 알고리즘은 최적해를 보장하지는 않지만, 일부 문제에서는 최종적 해답을 구할 수 있는 간단하고 효과적인 방법이 될 수 있습니다.
보통 그리디 알고리즘은 다음과 같은 구성으로 이루어집니다:
- 선택 단계(Selection phase): 현재 상황에서 가장 최선의 선택을 합니다.
- 적절성 검사 단계(Feasibility check phase): 선택한 단계가 해결하고자 하는 문제의 조건을 만족시키는지 확인합니다.
- 해결 단계(Solution phase): 문제의 해를 구하거나 다음 선택 단계로 이동합니다.
그리디 알고리즘을 사용할 수 있는 대표적인 문제로는 다익스트라 알고리즘, 크루스칼 알고리즘, 프림 알고리즘이 있습니다.
탐욕 알고리즘을 적용해 해결하기 위해서는 문제는 다음 2가지 조건을 성립하여야 한다.
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.
개발공부중