보호되어 있는 글입니다.

최소 신장 트리(MST, Minimum Spanning Tree)는 그래프 내의 모든 정점을 연결하는 최소 비용의 간선 집합으로 이루어진 트리를 의미합니다. 즉, 그래프의 모든 노드를 최소 비용으로 연결하는 것입니다.1. MST의 특징모든 정점이 연결되어 있어야 합니다.사이클을 포함해서는 안 됩니다.최소한의 비용으로 구성됩니다.2. MST 알고리즘 종류최소 신장 트리를 구하는 대표적인 알고리즘은 다음과 같습니다.2-1. 크루스칼(Kruskal) 알고리즘시간 복잡도: O(ElogE)간선의 비용을 기준으로 오름차순으로 정렬한 후, 사이클을 형성하지 않도록 최소 비용 간선을 순차적으로 선택합니다.2-2. 프림(Prim) 알고리즘시간 복잡도: O(ElogV)시작 정점에서부터 시작하여 연결된 정점들 중 최소 비용..

최소 공통 조상(LCA, Lowest Common Ancestor) 이란 트리에서 두 노드의 가장 가까운 공통 조상을 의미합니다. 이는 트리 구조에서 두 노드 간의 관계를 파악하거나 최단 거리 등을 찾을 때 유용하게 사용됩니다.1. 최소 공통 조상의 필요성트리에서 두 노드 간의 관계 파악효율적인 최단 경로 탐색2. LCA 알고리즘의 종류LCA를 구현하는 대표적인 방법은 다음과 같습니다.1. 단순 탐색시간 복잡도: O(N)가장 간단한 방법으로, 루트에서부터 탐색하여 두 노드의 공통 조상을 찾습니다.2. 이진 트리에서의 재귀적 탐색시간 복잡도: O(N)트리를 한 번 순회하면서 두 노드의 공통 조상을 찾습니다.3. Sparse Table (희소 테이블)시간 복잡도: 전처리 O(NlogN), 쿼리 O(logN)..