탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘이란?말그대로 Greedy하게, 탐욕스럽게 그 때 그 때의 최적의 상황을 쫓아 문제를 해결하는 방법이다.여러 경우 중 하나를 결정해야할 때 그 순간에 최적이라고 생각되는 것을 선택해나가며 최종 해답에 도달한다. 알고리즘을 적용하기 위한 전제 조건1) 탐욕적 선택 속성 (Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.2) 최적 부분 구조 (Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 문제 해결 절차1) 선택 절차 (Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.2) 적절성 검사 (Feasibility Check): 선택된 해가 문제의 조건..