탐욕법
-
[알고리즘] Greedy(탐욕법)SW/Algorithm 2018. 1. 6. 11:55
Greedy Algorithm (탐욕) 정의 : 매 선택에서 지금 이 순간 당장 최적인 해를 구함. 동적 계획법과 마찬가지로 최적화 문제를 푸는데 사용. 근시안적으로 해를 구할 당시에 가장 최적인 해를 구함. 동적 계획법처럼 반드시 최적의 해를 구한다는 보장이 없다. 한번의 선택이 다음 선택에서는 전혀 무관한 값이여야 하는 매순간의 최적해가 문제의 최적해. 과정 선택 : 현 상태에서 최적해에 포함시킬 대안을 선택 타당성 조사 : 선택된 해가 주어진 문제의 조건을 만족하는지 검사 해답 조사 : 원래의 문제가 해결되었는지를 조사 WHEN? 탐욕 알고리즘을 사용해 최적의 답을 구할 수 있다는 것이 쉽게 보이면 탐욕 알고리즘을 사용할 수 있는지가 의심스럽고 다른 알고리즘으로 답을 구할 수 있는 경우 사용X 탐욕..