Greedy Algorithm.md

Greedy Algorithm

• 그리디 알고리즘(탐욕알고리즘)

• 선택의 순간마다 당장 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

• 순간마다 하는 선택은 그 순간에 대해 지역적으로 최적이지만, 그 선택들을 계속 수집하여 전역적인 해답을 만들었다고 해도 그것이 최적이라는 보장은 없음

• 그리디 알고리즘 문제를 해결하는 방법

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

• 그리디 알고리즘을 적용하기 위한 2가지 조건

  - 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건과 최적 부분 구조 조건이라는 두 가지 조건이 만족됌.
  - 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다.
  
  1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
  

  관련 문제 : 도서관-풀이

  참고 블로그 : [알고리즘] 탐욕 알고리즘(Greedy Algorithm)