Algorithm - Greedy

Greedy Algorithm

• Greedy Algorithm
  • 여러 경우 중 하나를 결정해야할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘
  • 순간마다 하는 선택은 그 순간에 대해서 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 전역적인 해답을 만들었다고 해서 그것이 최적이라는 보장은 없음
  • greedy algorithm을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들임

Greedy Algorithm 문제 해결 과정

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

Greedy Algorithm을 적용하기 위해서 문제가 만족해야 하는 조건

• 탐욕 알고리즘이 잘 작동하는 문제는 아래의 두 가지 조건을 만족함

  1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후 선택에 영향을 주지 않음
  2. 최적 부분 조건(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제의 최적 문제 해결 방법으로 구성됨
     (문제에 대한 최적해가 부분 문제에 대해서도 최적해임)

• 이러한 조건이 설립하지 않은 경우, Greedy Algorithm은 최적해를 구하지 못함

  • Greedy Algorithm은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할수 있으므로 근사 알고리즘으로 사용할 수 있음
    • 근사 알고리즘(Approximation Algorthm) : 어떤 최적화 문제에 대한 근사값을 구하는 알고리즘

참고

• 탐욕 알고리즘(Greedy Algorithm)