그리디 알고리즘이란,
선택지를 결정할 때마다 그 때 최적인 값을 선택하는 방식으로 최적해를 구할 때 사용되는 근사적인 방법론이다.
💡알고리즘 원리💡
간단하게 설명하면 그리디 알고리즘은 당장 눈앞의 결정을 할 때 현재 최적이라고 생각되는 선택지를 고르면 결국 최적의 결과를 얻을 수 있다는 논리로 접근하며 최적해를 찾는 방법론이다.
그래서 그리디 알고리즘이 항상 최적해를 도출한다고는 할 수 없지만 최적해에 근사한 값을 도출할 수 있다고 본다.
🏷️주요 속성
그리디 알고리즘은 2가지 속성을 필요로 한다. 이 속성을 만족하지 않으면 그리디 알고리즘으로 최적해를 구할 수 없다.
🔘 탐욕 선택 속성 Greedy Choice Property
"각 결정 단계에서 최선을 선택하는 것이 결과적으로 최적해로 이어진다."
매 단계의 결정에서 최선의 선택을 하면 이는 결국 전체 문제의 최적해를 찾는 방향으로 연결된다는 속성이다.
🔘 최적 부분 구조 속성 Optimal Substructure Property
"주어진 문제의 최적해가 하위 문제의 최적해로 구성된다."
주어진 문제를 하위 문제 단위로 나누었을 때 각 하위 문제의 최적해를 포함할 때 전체 문제의 최적해를 찾을 수 있다는 속성이다.
🔗동작 과정
- 문제의 최적해를 선택하는 기준을 결정한다.
- 문제의 구조에 맞는 선택 절차를 정의하고 수행한다.
선택 절차 Selection Procedure
: 현재 상태에서 최적인 선택을 한다. 이 선택은 바뀌지 않는다. - 조건을 만족하는지 검사하여 만족하지 않는 해를 제외한다.
적절성 검사 Feasibility Check
: 선택한 항목이 최적해 선택 기준에 부합하는지 확인하고, 기준을 만족하지 않는 항목을 제외한다. - 선택이 완료되면 해답이 조건을 만족하는지 검사한다.
해답 검사 Solution Check
: 선택이 완료되면, 최종선택이 문제의 조건을 만족하는지 확인한다. 조건을 만족하지 않으면 선택 절차로 돌아가 과정을 반복하고,
조건을 만족하면 해답으로 선택한다.
🔎알고리즘 특징🔎
🔘 각 결정 단계에서 최선으로 판단되는 한 번의 선택을 한다.
그래서 구현이 쉽고 타 알고리즘에 비해 처리 속도가 빠르다.🔘 이미 결정한 선택은 다시 고려하지 않는다.
🔘 일반적으로 최적해를 도출하지 못한다.
그래도 언제나 최적해를 구할 수 있는 문제 구조(매트로이드)가 존재하기 때문에 탐욕 알고리즘을 활용할 수 있다.🔘 도출한 해를 설명하기 어렵다.
