미식가의 개발 일기

최소 신장 트리(MST, Minimum Spanning Tree)란?"그래프의 모든 정점을 최소한의 간선으로 연결하되, 간선들의 가중치 합이 최소가 되는 트리"  구성 요소 1. 무방향 가중치 그래프: 간선이 방향성을 가지지 않고, 가중치가 있는 경우  정점: 연결하려는 대상간선: 두 정점 A --(5)-- B| |(2) (3)| |C --(4)-- D  2. 신장 트리 (Spanning Tree): 그래프의 모든 정점을 포함하면서, 사이클 없이 연결된 부분 그래프                                                  -> N개의 정점을 연결하려면 최소 N-1개의 간선이 필요하다. 3. 최소 신장 트리 (Minimum Spanning..

유니온 파인드(Union-Find) 알고리즘이란?"서로소 집합(Disjoint Set)을 효율적으로 관리하는 자료구조"[서로소 집합: 공통 원소가 없는 집합]"두 원소가 같은 집합에 속해 있는지 확인하고, 두 집합을 합치는 작업을 빠르게 수행한다." 주요 연산 1. Find(찾기)어떤 원소가 속한 집단의 대표 원소(루트)를 찾는다.두 원소가 같은 집단에 속해 있는지 확인할 수 있다. 2. Union(합치기)두 집합의 루트를 찾아 하나의 집합으로 합친다.-> 이 2가지 기법만 가지고 구현하면 트리의 깊이가 깊어질 수 있다. 매번 한 트리의 루트에 다른 트리를 연결하면 트리의 높이가 증가하여 Find 연산이 비효율적으로 수행되므로 최적화 기법이 필요하다.  최적화 기법  1. 경로 압축(Path Compre..