Greedy algorithm(탐욕 알고리즘)

Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

 

< 적용 조건 >

- 전체 문제 해결에 대한 최적해가 부분 문제에 대한 최적해와 가까운 관계(유사한 답)를 유지하고 있다는 조건 필요 

- 탐욕 선택 속성을 갖고 있는 최적 부분 구조의 문제 
 탐욕 선택 속성 : 앞의 선택이 이후 선택에 영향을 주지 않아야 한다. (선택을 다시 고려하지 않음) 

 최적 부분 구조 : 문제의 최적 해결 방법이 부분문제에 대한 최적 해결 방법으로 구성되는 경우 

 

위의 조건을 만족하는 문제에 대해서 대부분의 경우 계싼 속도가 빠르며 그렇지 않은 문제에 대해서 근사한 해를 찾는 용도로 이용 

 

 

예시) 

 

1. 트리 구조에서의 합이 가장 큰 경로 탐색