0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 최소 신장 트리 (MST) Kruskal Prim 2. 제출 MST를 구하는 문제다. 주어지는 가중치가 크기 때문에 overflow를 주의하면서 풀면 된다. 가. Kruskal import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class SWEA3124 { static int V, E; static long ret; // int overflow 발생 sta..

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..