Greedy "탐욕스러운, 욕심 많은"
Greedy Algorithm
선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법.
탐욕 알고리즘으로 문제를 해결하는 방법
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
- 적절성 검사(Feasibility Check): 선택된 해답이 문제의 조건을 만족하는지 검사
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고,
해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
탐욕 알고리즘은 문제 해결 과정의 매 순간, 최적이라 생각되는 해답을 찾으며,
이를 통해 최종 해답에 도달하는 문제 해결 방식이지만 '특정한 상황'이 아니라면 최적의 결과를 보장하지는 못한다.
그러나 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
탐욕 알고리즘으로 최적의 해를 얻으려면 2가지 조건이 성립되어야 한다.
탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않고,최적 부분 구조: 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성되어야 한다.
그리디 알고리즘의 대표적인 예제는 거스름 돈 문제이다.
'무조건 더 큰 화폐 단위부터 거슬러 준다'는 알고리즘을 지키면 최적의 해를 보장할 수 있다.
이렇게 그리디 알고리즘은 기본적으로 무조건 큰/작은/긴/짧 경우대로 등 극단적으로 문제에 접근한다는 점에서 정렬(sort)기법이 함께 사용되는 경우가 많다.
