Greedy 알고리즘

Greedy 알고리즘

• 최적의 해답만을 고려하여 최종적으로 해답에 도달하는 알고리즘.
• 그리디 알고리즘은 다음의 단계로 나눌 수 있다.
  1. 선택절차
     • 현재 상태에서 최적이라고 생각하는 해답을 찾는다.
       → Locally Optimal Solution
  2. 적절성검사
     • 선택한 해답이 문제의 조건에 만족하는지 검사한다.
  3. 해답검사
     • 주어진 문제의 해결 여부를 검사하고, 아니라면 위의 과정을 반복한다.
     • 이 과정에서 최종 문제의 해답 Globally Optimal Solution 에 도달한다.
• 그러나 그리디 알고리즘은 항상 최적의 결과를 보장하지는 못하며, 아래의 조건을 만족하는 경우 최적의 결과를 얻을 수 있다.
  1. 앞의 선택이 이후의 선택에 영향을 주지않는 경우
     → 탐욕적 선택 속성
  2. 문제의 최종해결 방법이 최적 문제해결 방법으로 구성되는 경우
     → 최적 부분 구조

특징

• 무조건 큰 경우, 무조건 작은 경우, 무조건 긴 경우, 무조건 짧은 경우 등 극단적으로 문제에 접근한다.
• 위의 특징에 따라 정렬과 함께 사용되는 경우가 잦다.