그리디 알고리즘

greedy 알고리즘은 매 결정 순간 비용이 적은 것을 선택하는 알고리즘이다. 

 

그리디 알고리즘은 이전의 탐욕 선택이 이후 선택에 영향을 주지 않는 문제에서 자주 사용된다. (독립적)

왜냐, 최적해에 근사한 값일 뿐 최적해를 만족하지 못한다. A-B가 B-C경로에 영향주지 않음.

 

또, 전체 최적해가 부분 문제에 대해서도 최적해를 만족하는 문제에서 사용된다. 

A-B 와 B-C은 전체인 A-C최적해의 부분 문제가 되기 때문에 그리디 알고리즘을 적용하기 적절한 문제다. 

 

예시 그림 ㅎ

그렇지만 속도가 매우 빨라 동적계획법과 그리디 알고리즘이 혼용되어 쓰이기도 한다. 

---

이제 그리디 알고리즘 풀어야지...

 

참고한 블로그 

st-lab.tistory.com/143