codinging

MST Spanning Tree 란 모든 노드를 포함하는 부분 그래프이다. Minimum이 추가된 Minimum Spanning Tree 는 간선의 합이 가장 작고 모든 노드를 지나는 부분 그래프를 말한다. Minimum Spanning Tree를 구하는 알고리즘은 Kruskal , Prim 알고리즘이 있다. 백준 1197 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net Kruskal Algorit..

Union Find 유니온 파인드란 그래프의 관점에서 두 노드가 같은 그래프에 속하는지 빠르게 판별하는 알고리즘이다. 집합에서의 관점으로는 두 요소가 같은 집합에 속하는지 판별한다. union find 알고리즘은 두 노드가 속하는 집합을 합치는 union 과 두 노드가 같은 집합인지 확인하는 find 연산이 있다. 설명 6개의 노드로 union find 의 예시를 들어보겠다. 부모를 알 수 있는 배열을 만드는데, 각 노드는 아직 아무 연결도 되어있지 않으므로 아직 자기자신이 부모이다. 1,2를 한 집합으로 4,5,6을 한 집합으로 묶고자 한다. 먼저 위의 예시는 잘못된 예시이다. 만약, 이런식으로 부모 노드를 연결한다면 문제가 생길 것 이다. 모든 노드를 연결 한다고 가정했을때 위와 같은 방식으로 부모노..