알고리즘 - 그리디01 그리디(Greedy) 알고리즘이란?

그리디(Greedy) 알고리즘 이란

- 그리디(Greedy) 알고리즘이란 탐욕알고리즘이란 뜻으로 각 단계에서 최선책만을 선택하며 다음단계로 진행하는 알고리즘을 말한다.

- 최적의 해를 구하는 알고리즘은 아니다 최적의 해의 근사의 해를 구하는 알고리즘이다.

- 동적프로그래밍이 지나치게 많은 일을 하는 것에서 착안하여 고안된 알고리즘이며 동적프로그래밍을 대체하는 것은 아니고 서로 보완하며 사용되는 알고리즘이다.

- 각 단계에서 최선책만을 선택하기 때문에 현재의 선택에 의해 다음 단계의 조건이 변하는 경우에는 부적합한 알고리즘이다.

 

 

최적의 해가 아닌 이유?

- 그리디 알고리즘은 당장 선택할 수 있는 경우중 최선의 선택을 하기 때문이다. 예를 들어 지금 당장 금을 팔면 1돈에 10000원인데 내일은 1돈에 12000원인 경우 그리디 알고리즘은 당장 10000원에 팔게된다.

 

 

사용가능한 경우

1. 다익스트라 알고리즘

 

2. 활동 선택 문제

 

3. 분할가능 배낭문제