[알고리즘] Greedy Algorithm (탐욕 알고리즘)

Greedy Algorithme이란?

  - 미리 정한 기준에 따라 가장 좋은 답을 선택하는 알고리즘

  - 최적화 문제를 푸는데 사용

  - 근시안적으로 판단하고 해를 구하기 때문에 가장 최적의 해를 구하는 보장이 되지 않는다

  - 탐욕 알고리즘은 근사 알고리즘으로 사용하거나, 항시 최적의 해는 아니지만 계산 속도가 빠르다

 

Greedy 알고리즘 사용처 (탐욕 알고리즘이 잘 작동하기 위해)

  - 탐욕스런 선택 조건(Greedy choice property)과 최적 부분 구조 조건 (Optimal substructure) 
     이라는 두 가지 조건이 만족되야한다.

  - 탐욕스런 선택 조건 : 선택들이 이후의 선택에 영향을 주지 않는다는 뜻 
     예시 ) 잔돈 800원을 만들기 위해 500원을 집어 들었다. // 최초의 선택
               300원이 모잘라 100원을 집어 들었다.                 // 이전에 선택이 영향 받지 않음

  - 최적 부분 구조 조건 : 해결하려는 문제가 최적의 해를 구하는 문제여야 한다는 조건