탐욕법(Greedy) 알고리즘

• 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘
• dp를 간단한 문제해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안
• 현재의 최선의 선택이 최종적인 결과 도출에 대한 최적해를 보장해주는 것은 아님

최선의 선택

       시작
      /    \
    17      6       <- 최선 17
   / \     / \
  23  4  128 16		<- 최선 23
  

- 가장 큰 수에 도달하기 위해 매번 큰 수를 선택하는 것 (시작 - 17 - 23)  Greedy!
- 그러나 결과적으로 가장 큰 수에 도달하는 방법은 (시작 - 6 - 128)       Best!

-> 최선의 선택이 반드시 최적해는 아닐 수 있음

그리디 알고리즘 조건

• 최선의 선택이 반드시 최적해는 아닐 수 있으므로 그리디 알고리즘을 사용하기 위한 조건 필요

1. 탐욕스러운 선택 조건

   • 탐욕적인 선택이 항상 안전하다는 것이 보장되어야 함
     (이 선택으로 최적해에 반드시 도달해야 함)

2. 최적 부분 구조 조건

   • 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결이어야 함

3. 값들이 서로 영향을 주면 안된다는 것

그리디