CS(Computer Science)/알고리즘
알고리즘 - 그리디01 그리디(Greedy) 알고리즘이란?
galid1
2019. 3. 18. 18:04
728x90
그리디(Greedy) 알고리즘 이란
- 그리디(Greedy) 알고리즘이란 탐욕알고리즘이란 뜻으로 각 단계에서 최선책만을 선택하며 다음단계로 진행하는 알고리즘을 말한다.
- 최적의 해를 구하는 알고리즘은 아니다 최적의 해의 근사의 해를 구하는 알고리즘이다.
- 동적프로그래밍이 지나치게 많은 일을 하는 것에서 착안하여 고안된 알고리즘이며 동적프로그래밍을 대체하는 것은 아니고 서로 보완하며 사용되는 알고리즘이다.
- 각 단계에서 최선책만을 선택하기 때문에 현재의 선택에 의해 다음 단계의 조건이 변하는 경우에는 부적합한 알고리즘이다.
최적의 해가 아닌 이유?
- 그리디 알고리즘은 당장 선택할 수 있는 경우중 최선의 선택을 하기 때문이다. 예를 들어 지금 당장 금을 팔면 1돈에 10000원인데 내일은 1돈에 12000원인 경우 그리디 알고리즘은 당장 10000원에 팔게된다.
사용가능한 경우
- 다익스트라 알고리즘
- 활동 선택 문제
- 분할가능 배낭문제