[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 최적해를 구하는 데에 사용되는 근사적인 방법이다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서 그것이 최적이라는 보장은 없다.
하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.