1. 그리디 알고리즘(탐욕법, Greedy Algorithm)
💡 그리디 알고리즘(탐욕법, Greedy Algorithm) 이란?
- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 '각 단계에서 최적
이라고 생각되는 것을 선택' 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고
리즘이다.
- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 '근사한 값' 을 목표로 하고
있다.
- 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를
결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
💡 [문제] 노드에서 가장 합이 높은 방법을 선택하는 방법을 생각해 보자.
💡 해당 경우에서는 그리디 알고리즘과 같은 형태로 노드를 선택하는 방식이다.
💡 각각 상황에서 '최적' 이라고 생각하는 방법을 선택한다. (상황에서 가장 높은 수를 선택)
💡 근시안적 방법론이란?
- 단기적인 목표를 중심으로 한 전략적인 접근 방법을 의미합니다.
이 방법론은 주로 현재의 문제를 해결하는 데 초점을 맞추며, 장기적인 전망보다는
단기적인 성과를 중요시합니다.
💡 근사 알고리즘(Approximation Algorithm) 이란?
- 최적의 해를 구할 수 없는 문제에서 근사한 해를 구하는 알고리즘을 의미합니다.
근사 알고리즘은 항상 최적해를 보장하지는 않지만, 많은 경우에는
최적해에 근접한 값을 구할 수 있습니다
2. 그리디 알고리즘 주요 속성
💡 문제를 풀 때 두 가지 조건이 성립해야 그리디 알고리즘을 적용할 수 있다.
- 탐욕 선택 속성 (Greedy Choice Property)
💡 탐욕 선택 속성 이란?
- 각 단계에서 '최선의 선택' 을 했을 때 전체 문제에 대한 최적해를 구할 수 있는
경우를 말한다. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의
결과를 가져온다는 것이다.
- 최적 부분 구조 (Optimal Substructure)