ℹ️ 개요 : 그리디 알고리즘이란
탐욕 알고리즘이라고도 하며, 말 그대로 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법이다. 그렇기 때문에 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서 그것이 최적이라는 보장은 없다.
동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘으로, 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.
🚩그리디 알고리즘이 동작하는 곳
그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다.
- 탐욕적 선택 속성(greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(optimal substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.
그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들에 해당한다.
위와 같은 문제의 구조를 매트로이드라고 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니지만, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여준다.
📒 그리디 알고리즘 문제를 해결하는 방법
- 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위 과정을 반복한다.
🤨 근사 알고리즘으로서의 그리디
근사 알고리즘(approxiamtion algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.
어떤 문제가 탐욕적 선택 속성과 최적 부분 구조를 갖추지 않는다면 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만 이러한 경우 탐욕 알고리즘은 근사 알고리즘을 사용이 가능할 수 있으며, 대부분의 경우 계손 속도가 빠르기 때문에 실용적으로 사용할 수 있다.
❓그리디 알고리즘이 사용되는 예시
- AI에 있어서 결정 트리 학습법(Decision Tree Learning)
- 활동 선택 문제(Activity selection problem)
- 거스름돈 문제
- 최소 신장 트리(Minimum spanning tree)
- 제약조건이 많은 대부분의 문제
- 다익스트라 알고리즘
- 허프만 코드
- 크러스컬 알고리즘
📚 REFERENCE
