[Greedy] 탐욕적 알고리즘

탐욕 알고리즘(Greedy Algorithm)

최적해를 구하는 데에 사용되는 근사적인 방법

여러 경우 중 하나를 결정해야 할 때마다 그때마다 최적의 방법을 선택하여 최종 해답에 도달하는 방법

매 순간마다 최적의 선택을 하더라도 최종적 해답이 최적이라는 보장은 없다

(각 순간의 지역적 선택이 최적일지는 몰라도 전역적으로 봤을때는 최적의 선택이 아닐 수 있다)

 

탐욕 알고리즘 적절한 사용

탐욕 알고리즘은 아래 두 경우에 사용할 때 좋은 해결방안이 된다

• 탐욕 선택 속성(Greedy Choice Property) : 매 순간의 탐욕적인 선택이 최종 답의 최적의 선택이 됨
• 최적 부분 구조(Optimal Substructure) : 부분 문제를 최적화하는 것이 전체를 최적화하는 것임

즉 탐욕 알고리즘을 사용할 때는 한 번의 선택이 다음 선택에 전혀 무관한 값이어야 하며,

순간의 최적해가 문제에 최적해가 되는 경우에 적합하다

 

근사 알고리즘

어느 경우에도 탐욕 알고리즘은 100% 최적 해를 보장해주지 않는다

하지만 어느정도 적합한 수준의 해답을 구할 수 있기 때문에 어느 정도의 손실을 감안하고 사용할 수 있다

 

[참고]

나무위키 : https://namu.wiki/w/그리디%20알고리즘

블로그 : https://codingmoonkwa.tistory.com/31