[심화] 그리디 알고리즘

그리디 알고리즘

개념

최적해를 구하는 데에 사용되는 근사적인 방법
각 선택의 순간마다 최적이라고 생각되는 것을 선택
지역적 최적해
전역적 최적해가 아닐 수 있음

장점

빠른 연산 속도

적용 상황

1. 그리디 알고리즘으로 최적해를 구할 수 있는 상황

• 탐욕스런 선택 조건 greedy choice property
  앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조 조건 optimal substructure
  문제 최적해가 부분 문제에서도 최적해

2. 근사 알고리즘

3. 매트로이드
   특별한 구조를 가짐
   언제나 최적해를 갖는 탐욕 알고리즘