(23.03.24) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 5.1 Minimum spanning trees -> prim's algorithm Prim's algorithm - dijkstra와 비슷한 방법으로 priority queue를 사용한다. - priority queue에다가 weight를 저장하여 가장 작은 weight을 가진 노드를 꺼내는 방식으로 진행한다. 꺼낸 노드에 인접한 노드의 cost와 edge의 weight을 비교하여 더 적은 값으로 업..

(23.03.20-22) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 5.1 Minimum spanning trees -> kruskal's algorithm -> cut property -> Union Find Greedy algorithm 매 순간마다의 최선의 선택을 하는 방법인데, 매순간마다의 그 최선의 선택이 결국 최종적으로 최선의 선택이 된다는 보장은 없다. top-down 방식으로 최선의 선택을 하는 것이다. 다시 말하면 아래와 같다. "solution ..