탐욕 알고리즘(Greedy Algorithm)

매 선택마다 지금 이 순간의 최적인 답을 선택하는 것이다.
단, 매 선택이 순간마다는 최적의 답이지만 종합적으로 봤을 때 최적이라는 보장은 절대 없다.

탐욕 알고리즘을 위한 2가지 조건

탐욕적 선택 속성

앞의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조

문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

• 두 조건이 만족하지 않을 때, 탐욕 알고리즘은 최적의 해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있고, 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.

근사 알고리즘(Approximation Algorithm)

최적의 해를 구할 수 없는 문제에서 근사적인 해를 구하는 알고리즘이다.
-> 어느 정도 보장된 근사적인 해를 구할 수 있다.