ITPE * JackerLab

개요프림 알고리즘(Prim Algorithm)은 그래프에서 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는 대표적인 그리디 알고리즘으로, 하나의 정점에서 시작하여 인접한 최소 비용 간선을 반복적으로 선택하며 트리를 확장하는 방식이다. 네트워크 설계, 회로 최적화 등 다양한 분야에서 활용된다.1. 개념 및 정의프림 알고리즘은 하나의 시작 정점을 선택한 후, 현재 트리에 포함된 정점들과 인접한 간선 중 최소 비용 간선을 선택하여 점진적으로 MST를 구성하는 방식이다. 크루스칼 알고리즘과 달리 노드 중심 접근 방식을 사용한다.2. 특징항목설명비고노드 중심 방식시작 정점 기준 확장크루스칼과 차별화그리디 알고리즘최소 간선 선택 반복최적해 보장우선순위 큐 활용최소 간선 선택성능 최적화한줄..

개요크루스칼 알고리즘(Kruskal Algorithm)은 그래프에서 최소 비용으로 모든 정점을 연결하는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 대표적인 그리디 알고리즘이다. 간선을 비용 기준으로 정렬한 후 사이클이 발생하지 않는 범위 내에서 선택하는 방식으로 동작하며, 네트워크 설계 및 최적화 문제에서 널리 활용된다.1. 개념 및 정의크루스칼 알고리즘은 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한 뒤, 가장 작은 간선부터 선택하면서 사이클을 형성하지 않는 경우에만 트리에 포함시키는 방식이다. 이를 위해 Union-Find(Disjoint Set) 자료구조가 필수적으로 사용된다.2. 특징항목설명비고그리디 알고리즘최적 선택 반복전역 최적 보장간선 중심 처리노드가 아..

개요Disjoint-Set(또는 Union-Find)은 원소들이 속한 집합을 관리하고, 두 원소가 같은 집합에 속하는지 여부를 빠르게 확인하는 자료구조입니다. 동적 집합 관리, 그래프 연결성 판별, 최소 신장 트리(MST) 알고리즘(크루스칼 등)에서 핵심적으로 사용되며, 경로 압축(Path Compression)과 랭크 기반 합치기(Union by Rank) 기법을 통해 효율성을 극대화할 수 있습니다.1. 개념 및 정의 항목 내용 정의여러 원소들을 비중복 집합으로 나누고, 집합 간 합치기 및 같은 집합 여부를 빠르게 판별하는 자료구조목적집합의 동적 결합 및 멤버십 판정 최적화필요성복잡한 집합 연산을 매우 빠르게 처리하여 그래프 및 집합 문제 해결Disjoint-Set은 복잡한 관계성을 효율적으로 관리하..