Greedy Algorithm(탐욕 알고리즘)

안녕하세요 : ) 오늘은 탐욕 알고리즘에 대해 알아봐요 

 

Greedy Algorithm : 최적의 해를 구하는데 사용하는 방법.

여러 가지 경우 중 하나를 결정해야할 때마다 최적이라고 생각되는 것을 골라 최종결과를 도출해낸다.

각 선택의 시점에서 내린 결정이 최적이라고 해서 최종 결과 또한 최적이라는 보장은 성립하지 않는다.

 

Greedy Algorithm의 과정:

1. 해 선택 : solution set(부분 해 집합)에 각 선택 시점에서 구한 최적해를 추가.

2. 실행 가능성 검사 : 새로운 solution set이 문제의 조건을 위반하지 않는지 검사하여 실행 가능성을 판단.

3. 해 검사 : 새로운 solution set이 문제의 해가 되는 지 검사한다. false이면 다시 해 선택 단계부터 시작한다.