ITPE * JackerLab

개요Link-Cut Tree는 동적으로 연결되거나 분리되는 트리 구조에서 효율적으로 경로 질의 및 갱신 연산을 수행할 수 있도록 설계된 고급 트리 기반 자료구조입니다. Sleator와 Tarjan에 의해 1983년 제안된 이 자료구조는 splay tree를 기반으로 하며, 각 노드의 서브트리나 루트까지의 경로에 대해 로그 시간 내 연산을 지원합니다. Union-Find, Euler Tour Tree보다 더 복잡한 트리 동작이 필요한 알고리즘에 적합합니다.1. 개념 및 정의 항목 설명 정의Link-Cut Tree는 포레스트(트리들의 집합) 구조에 대해 노드 간 연결(Link), 분리(Cut), 경로 질의(Query), 경로 갱신(Update)을 동적으로 처리하는 트리 자료구조입니다.목적트리 구조가 변동하..

개요Fibonacci Heap은 그래프 알고리즘에서 중요한 역할을 하는 우선순위 큐 구현 구조로, 특히 Decrease-Key, Merge 연산에서 탁월한 이론적 성능을 보이는 자료구조입니다. 이름은 노드 수가 피보나치 수열을 따르는 구조적 특성에서 유래하며, Dijkstra, Prim 알고리즘의 이론적 시간 복잡도를 낮추는 데 핵심 역할을 합니다.1. 개념 및 정의Fibonacci Heap은 연결 리스트 기반의 느슨한 구조로 구성된 **최소 힙(min heap)**이며, 여러 개의 트리를 루트 리스트로 구성하고 lazy 방식으로 병합 및 삽입을 처리합니다.창시자: Fredman과 Tarjan (1984)특징: 느슨한 균형 유지, 지연된 구조 조정(lazy consolidation)용도: 최단 경로 탐색..

개요Heavy-Light Decomposition(HLD)은 트리 구조에서 경로 쿼리(Query)나 업데이트(Update)를 빠르게 처리하기 위해 고안된 분할 기법입니다. 트리의 간선을 무거운(Heavy) 간선과 가벼운(Light) 간선으로 분류하여, 경로를 소수의 구간(segment)으로 분해하고, 각 구간에 대해 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree) 같은 자료구조를 적용하여 O(log² n) 또는 O(log n) 시간 복잡도로 효율적인 처리를 가능하게 합니다.1. 개념 및 정의 항목 내용 정의트리를 Heavy 간선과 Light 간선으로 분할하여 경로 쿼리와 업데이트를 최적화하는 알고리즘적 테크닉목적트리 경로 질의의 시간 복잡도를 개선하여 고속 연산 지원필요성단..

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