탐욕 알고리즘

• 매 순간 최적 해를 선택하면서 최종적으로 최적해에 도달하는 알고리즘 설계 기법
• 탐욕 알고리즘 특징
  • 최적 부분 구조나 탐욕 선택 속성 문제를 해결하는데 적합하다.
  • 매 순간 최적 해를 찾으면서 구하는 방법이 항상 최적임을 보장하지 않아서 유의가 필요하다.
• 탐욕 알고리즘으로 문제 해결하는 방법
  • 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
  • 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
  • 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
• 탐욕 알고리즘 조건
  • 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
• 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이있다.