탐욕 알고리즘(greedy algorithm)은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 즉, 최적해를 구하는 데에 사용되는 근사적인 방법이다. 순간마다 하는 선택은 그 순간에 한해서는 최적이지만 그러한 선택들을 통해 최종적인 해답을 얻었다고 해서 그 해답이 최적이라는 보장이 없다. 예외의 상황이 있을 수 있기 때문이다. 따라서, 이러한 예외 상황을 배제하고 탐욕 알고리즘을 통해 최적의 해를 구하기 위해서는 다음과 같은 두 가지 조건을 만족시켜야 한다. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최적해가 부분문제에..