Greedy 알고리즘
Greedy 알고리즘?
문제를 해결하는 과정에서 순간마다 최적이라고 "생각되는" 결정을 하는 방식으로 최종 해에 도달하는 문제해결 방식이다. (최적해를 구하는 데 사용되는 근사적인 방법)
순간 최적의 결정이 전체 문제의 해결책이 되지는 않는다.
루트 노드로부터 리프 노드까지의 총 합의 최대값을 구하는 그림이지만 Greedy로는 풀이할 수 없다.
Greedy의 가장 큰 장점은 계산속도이다. Greedy 방법을 쓸 수 있는 몇몇 문제에서는 최적해를 가장 빠르게 산출해낼 수 있다.
탐욕스러운 선택 조건(Greedy choice property)
각 단계에서 탐욕적으로 내리는 선택이
항상최적해로 가는 방법이다.최적 부분 구조 조건(Optimal Substructure)
문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결방법이다. 즉! 결정할 때
탐욕적 선택이 문제 전체를 해결하는 방법이어야 한다는 것이다.
한번의 선택이 다음 선택에는 전혀 무관해야하며 매 순간 최적해가 문제에 대한 최적해야여야 한다.
DP와의 관계
DP와 Greedy는 Optimal Substructure라는 하위 문제를 해결했을 때 전체 문제를 해결할 수 있는 속성은 동일하다. 하지만 DP는 가능한 모든 방법을 고려해야 한다는 단점이 있기에 Greedy 알고리즘이 등장했다고 한다. 다만 Time Complexity는 DP가 더 높지만, 그 결과에 대해 보다 신뢰적이다.
Greedy는 DP 문제와 비슷한 경우가 많다.
따라서 시간 및 메모리의 제약이 심하다면 Greedy 알고리즘으로 의심해볼만 하다.
Greedy 대표적인 문제
Greedy는 탐욕적인 선택을 하는 만큼 정렬을 한 후에 푸는 경우가 일반적이다
- 활동선택문제
- 거스름돈 문제
- Kruskal
- Dijkstra
- Fractical Kanpsack (쪼개지는 배낭 문제)
Go to 문제정리가 잘된 블로그
