그리디 알고리즘이란 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm)

항상 최적의 해를 구하는 동적 계획법과는 다르게 그리디 알고리즘은 현재 단계에서 선택할 수 있는 최적의 선택만을 하여 답을 구성해나가는 방식이다. 그러나 이 방식은 결론적으로 최적의 해를 구한다고 단정지을 수 는 없다.
그리디 알고리즘과 동적 계획법은 상호보완적인데 그리디 알고리즘은 빠른 계산 속도 을 가지고 동적 계획법은 최적의 해 를 구한다는 점에서 장점이 있다.
그리디는 아래 두 가지 조건이 성립되어야 잘 작동할 수 있다.
- 탐욕스러운 선택 조건 (Greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는 조건
- 최적 부분 구조 조건(Optimal Substructure) : 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이다는 조건
그리디 알고리즘이 적용되는 대표적인 예시가 몇 가지 있다. 참고 사이트 두번째 링크에서 확인해볼 수 있다.
1. 활동 선택 문제 (The Activity-Selection Problem)
2. 분할가능 냅색 문제 (The Fractional Knapsack problem)