0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 최소 신장 트리 (MST) 2. 제출 이 문제는 모든 노드가 서로 연결될 수 있는 완전 그래프다. 따라서 많은 간선이 생길 수 있다. (E의 최대 개수 = (V(V-1))/2)) Kruskal으로 풀기 : 시간 복잡도 O(ElogE + V) : 간선이 많은 밀집 그래프에서 불리. Prim으로 풀기 PQ로 구현한 Prim : 시간 복잡도 O(ElogE) : 간선이 많은 밀집 그래프에서 불리. 반복문으로 구현한 Prim : 시간 복잡도 O(V^2) : 밀집 그래프에 유리! 밀집 그래프에서 유리한 반복문으로 구현한 Prim 알고리즘으로 문제를..

1. 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무향 그래프에서 n개 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 알고리즘 방식 시간 복잡도 유리한 상황 자료구조 Kruskal 일반적 O(ElogE + V) 간선이 많지 않은 그래프 간선 리스트 Prim (PQ 구현) 우선순위 큐(PQ) 사용 O(ElogV) 또는 O(ElogE) 간선이 많지 않은 그래프 인접 행렬, 인접 리스트 Prim (반복문 구현) 반복문 사용 O(V^2) 간선이 많은 밀집 그래프 인접 행렬, 인접 리스트 (E : 간선의 수, V : 정점의 수) But! PQ..