트리 최소 공통 조상 알고리즘
\(\texttt{0x00}\) 개념
루트 트리에서 노드 \(z\)가 노드 \(x\)와 \(y\)의 공통 조상일 때, \(x\)와 \(y\)의 모든 공통 조상 중 깊이가 최대인 노드를 **최소 공통 조상(LCA)**이라 하며 \(\text{LCA}(x,y)\)로 표기합니다.
\(\texttt{0x01}\) 계산 방법
1. 트리 이진 증가
접근법:
상향 표식법을 개선한 방법으로, 매 단계마다 \(2^k\) 레벨 상위 조상으로 이동합니다. \ ...
7월 17일 23:31에 게시됨
LCA (최소공통조상) 알고리즘 완벽 가이드
LCA (Lowest Common Ancestor)
LCA(최소공통조상)는 트리에서 두 정점의 가장 가까운 공통 조상을 찾는 문제이다. 트리 관련 알고리즘에서 가장基础的인 개념 중 하나이다.
1. 브루트 포스 방식
가장 간단한 접근법은 직접 위로 올라가며 찾는 것이다. 먼저 각 정점의 깊이(depth)와 부모 정보(fa)를 전처리한다.
알고리즘:
두 정점 u, v 중 더 깊은 정점을 찾는다.
...
7월 17일 22:27에 게시됨
트리 체인 분할을 이용한 알고리즘 구현 및 응용
개요
트리 체인 분할은 트리를 여러 체인으로 나누어 선형 자료구조를 활용할 수 있도록 하는 기법이다. 이 중 가장 널리 사용되는 방식은 Heavy-Light Decomposition(HLD)이다.
다음과 같은 개념들을 정의한다:
무거운 자식: 특정 노드의 모든 자식 중 서브트리 크기가 가장 큰 자식
가벼운 자식: 무거운 자식을 제외한 나머지 자식들
무거운 간선: 부모와 무거운 자식을 ...
7월 14일 21:25에 게시됨
Codeforces Round 864 (Div. 2) E. Li Hua and Array
문제 개요
배열의 각 원소에 대해 오일러 함수를 반복적으로 적용하면서, 특정 범위 내의 모든 원소가 동일한 값으로 수렴하는 최소 연산 횟수를 구하는 문제입니다. 이 과정에서 선형 시간 전처리와 세그먼트 트리, 그리고 LCA(Lowest Common Ancestor) 기법을 결합하여 효율적인 쿼리를 처리합니다.
핵심 아이디어
오일러 함수 φ(n)는 정수 n에 대해 1부터 n까지의 자 ...
6월 19일 02:59에 게시됨