오구리의 DevLog

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.12.08 - [컴퓨터공학/알고리즘2] - [알고리즘2] Minimum Spanning Tree(MST) [알고리즘2] Minimum Spanning Tree(MST) 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶구현 API 정리 # 이미 구현된 기능 class Edge: # Weight 있는 방향성 없는 간선 나타내는 클래스 (예..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents MST Greedy algorithm Kruskal's algorithm Prim's algorithm lazy version Prim's algorithm eager version ▶MST Minimum Spanning Tree : Wegiht 합이 최소인 spanning tree 1. Tree (connected and acyclic subgraph of G) 2. Spanning tree (모든 정점 포함) 3. 간선의 weight 합이 최소 Brute-force 알고리즘 : 모든 가능한 spannign ..