백준알고리즘
그리디 알고리즘
socialcomputer
2021. 4. 26. 20:08
반응형
greedy 알고리즘은 매 결정 순간 비용이 적은 것을 선택하는 알고리즘이다.
그리디 알고리즘은 이전의 탐욕 선택이 이후 선택에 영향을 주지 않는 문제에서 자주 사용된다. (독립적)
왜냐, 최적해에 근사한 값일 뿐 최적해를 만족하지 못한다. A-B가 B-C경로에 영향주지 않음.
또, 전체 최적해가 부분 문제에 대해서도 최적해를 만족하는 문제에서 사용된다.
A-B 와 B-C은 전체인 A-C최적해의 부분 문제가 되기 때문에 그리디 알고리즘을 적용하기 적절한 문제다.
그렇지만 속도가 매우 빨라 동적계획법과 그리디 알고리즘이 혼용되어 쓰이기도 한다.
이제 그리디 알고리즘 풀어야지...
참고한 블로그
반응형