탐욕법

탐욕법(이하 greedy) ?

 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말합니다. 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하는 개념으로 보시면 됩니다.

 

그리디 알고리즘의 해결 방안 ?

• 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
• 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
• 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

이런 식의 해결 방안이 있는 것을 확인 해 볼 수 있습니다.

 

그리디 알고리즘의 문제는 최적 문제를 항상 보장하는 것은 아니다. 때문에 그리디 알고리즘을 적용할 때 주의해야할 것은 해당 방법이 정당성을 가지고 있는가 를 정확하게 살펴 보아야 합니다.'

 

따라서

-탐욕 선택 속성(greedy choice property)

 -최적 부분 구조(optimal substructure)

 이 두가지의 특성을 가지는 문제들을 해결하기에 좋은 조건을 가지고 있음을 볼 수 있습니다.

 

 

•