그리디 알고리즘

그리디 알고리즘그리디 알고리즘의 핵심은 문제를 해결할 때 각 단계에서 매번 최선의 선택을 하는 것입니다. 당장 눈 앞의 선택지 중에 최선을 선택을 하여 결과적으로 최고/최적의 결과값을 도출해 내는 기법입니다. 이름이 Greedy Algorithm(탐욕 알고리즘)인 것을 생각해 보면 어느 정도 쉽게 이해가 됩니다. 그리디 알고리즘은 단계별로 그냥 최적의 선택만 하면 되기 때문에 단순하여 구현이 쉽다는 장점이 있습니다.  그리디 알고리즘에도 치명적인 단점이 존재합니다. 바로 매 순간 현재 단계에서 최선의 선택을 하더라도, 전체 문제의 관점에서 보았을 때 최선의 선택이 아닐 수 있다는 점입니다. 이런 점 때문에 그리디 알고리즘을 사용할 때는 아래의 조건을 충족하는 문제에서만 사용하여야 합니다. 1. 현재의 선..