개발일지

개념 MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다. => 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것 => 신장트리 : Cycle이 없는 그래프 Kruskal DisjointSet을 이용하여 MST를 갱신하며 구하는 알고리즘 작동원리 1. 모든 간선을 가중치 기준으로 오름차순으로 정렬한다. 2. 가중치가 작은 간선부터 확인하면서 간선에 속한 정점 v1, v2가 다른 SET이면 UNION하고 WEIGHT만큼 RESULT에 더한다. 시간복잡도 간선을 정렬 할 때 : O(ElogE) DisjointSet 사용할 때 : O(1) O(ElogE) 문제 16398 행성 연결 www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 ..

개념 MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다. => 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것 => 신장트리 : Cycle이 없는 그래프 Prim Heap을 이용하여 MST를 갱신하며 구하는 알고리즘 작동원리 1. 시작노드를 우선순위 큐에 PUSH한다. 2. 우선순위 큐에서 노드를 POP한다. 3. 체크되지 않은 노드라면 WEIGHT 값만 큼 RESULT에 더하고 갈 수 있는 노드중 체크되지 않은 노드를 우선순위 큐에 PUSH한다. 4. 2 ~ 3을 우선순위 큐가 EMPTY일 때까지 반복한다. 시간복잡도 O(ElogV) 문제 13418 학교 탐방하기 www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표..