탐욕적 알고리즘(Greedy Algorithm)이란?

오늘은 탐욕적 알고리즘(Greedy Algorithm)에 대해 공부했다.
탐욕적 알고리즘이 뭐냐면.. 매 선택의 순간마다 최적의 해답(locally optimal solution)을 찾고, 이를 토대로 최종 문제의 해답(globally optimal solution)에 이르는 알고리즘이다. 이는 항상 최적의 결과를 도출하는 건 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 그래서 탐욕적 알고리즘은 근사 알고리즘으로 사용할 수 있다.

탐욕적 알고리즘을 적용하는 방식은 다음과 같다.

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

탐욕적 알고리즘 적용의 조건 2가지!

1. 탐욕적 선택 속성 : 앞의 선택이 이후 선택에 영향을 주지 않아야 한다.
2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.