Greedy Algorithm (탐욕 알고리즘)

그리디 알고리즘이란?

문제를 해결하는 과정에서 매번 최적이라고 생각하는 방법으로 결정하는 태도라고 할 수 있을 것같다.

특별한 공식같은 건 없는 거같다. 그래서 이름이 Greedy인 것이 아닐까?

 

 

Greedy 알고리즘은

1. Greedy choice property
2. Optimal Substructure

위의 두 조건이 성립될 때 적용 가능하다.

 

<탐욕스러운 선택 조건 (Greedy choice property)>
 : 이 조건을 만족함은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이다.

 

<최적 부분 구조 조건(Optimal Substructure)>
 : 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것이다.