알고리즘설계기법 - 5. 탐욕법

분할 통치법

- 잘 파악된 부분을 조금씩 넓혀가 결과를 찾음

- 해에 접근하는 방법에 따라 능률이 좋거나 나빠지기도 함.

 

 

탐욕법 greedy algorithm

- 현재 상태에서 볼때 가장 좋은 경우를 따라가는 방법

- 당장의 성능 개선이 보임

- 지역적 최선의 선택이 전역적으로 좋다고 보장할 수 없음

=> 당장의 최적의 방향으로만 쫓다간 지역해에 수렴함. 전역해에 도달못하는 경우 발생

 

https://commons.wikimedia.org/wiki/File:Greedy-search-path-example.gif

 

 

 

탐욕법의 예시

1. 다익스트라 알고리즘

 

 

 

2. 프림 알고리즘

https://en.wikipedia.org/wiki/Prim%27s_algorithm