Prim
-
알고리즘 ch8 Greedy algotithm학교 수업/알고리즘 2020. 6. 15. 18:50
Optimization Problem- 여러개의 가능한 답 중에 가장 최적의 답 또는 최적의 답과 가까운 답을 고르는 문제- 비용을 최소화 한다거나 이익을 최대화 하는 답을 고르는 문제 Greedy Algorithm- 최적해를 구하는 데에 사용되는 근사적인 방법. - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (미래를 생각하지 않고 각 단계에서 최선의 선택을 함) Optimization problem 중 greedy 방법을 사용하는 문제1. Minimum Spanning Tree (MST) - Spanning tree 중 사용된 간선들의 가중치 합이 최소인 트리 즉, 그래프 내에 있는 모든 정점들을 가장 적은 수..