2018 04 29 Algorithm - RYUDONGJIN/Memo_wiki GitHub Wiki

[Algorithm] Greedy Method 또는 Algorithm에 대해 설명하십시오.

• 탐욕적 알고리즘(Greedy Method)은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 해답으로 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 것입니다. 순간마다 하는 선택은 그 순간에 대해 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다. 따라서 Greedy Method는 항상 최적의 해답을 주는지를 반드시 검증해야 합니다. 탐욕적 알고리즘의 설계 절차는 현재 상태에서 가장 좋다고 생각되는 해답을 찾아서 해답모음에 포함시키는 선정과정, 새로 얻은 해답모음이 적절한지를 결정하는 적정성 점검, 새로 얻은 해답모음이 최적의 해인지를 결정하는 해답점검의 절차가 있습니다.