[기술면접/알고리즘] Greedy Algorithm (탐욕법)

Greedy Algorithm (탐욕법)에 대해 설명하세요

Keyword

매 선택의 순간, 최적, 지역 최적해, 전역 최적해, 매트로이드

Script

Greedy 기법은 매 선택의 순간마다, 그 순간에 최적의 상황으로 나아가며 최종적인 해를 구하는 기법입니다. 항상 최적해를 구하는 것이 아닌, 최적해에 빠르게 근사하는 기법이라고 할 수 있습니다.

그래서 지역적으로 최적해를 찾아, 전역 최적해를 찾을 수 있는 문제들에서 유용하게 사용됩니다. 이런 문제를 매트로이드 구조를 가진 문제라고 하며, 최소 신장 트리를 찾는 크루스칼 알고리즘이나 프림 알고리즘에서 사용됩니다.

Additional