[Algorithm] 탐욕법(그리디) 알고리즘(greedy algorithm)

(1) 탐욕법(그리디) 알고리즘 이란?

매 선택에서 지금 이 순간 최적의 답을 선택하는 알고리즘이다.

단, 매 선택이 각 단계에서는 최적이지만 종합적으로 보았을 경우 최적이라는 보장이 없다.

예를 들어 매 순간 최적을 따라가게되면 1-1-1-100으로 갈경우 매 순간 최적이 아니더라도 1-1-10-10이 종합적으로 보았을 경우 더 최적일 수 있는 경우가 생긴다.

 

탐욕법(그리디) 알고리즘은 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해인 경우 문제를 해결하는데 강점이있다.

---