Trie 트리 최적화를 통한 문자열 집합 처리 기법
문제 개요
문자열과 연관된 값들의 집합이 주어졌을 때, Trie 자료구조를 활용하여 유효한 구조인지 판별하고 최소 노드 개수를 구하는 문제입니다.
무효 조건 분석
다음 상황에서는 유효한 Trie 구조를 구성할 수 없습니다:
동일한 문자열이 서로 다른 값을 가지는 경우
여러 값들이 동일한 LCA 노드를 공유하는 경우
루트에서 LCA 노드까지의 경로에 제한된 노드가 존 ...
10월 9일 01:37에 게시됨
트리 최소 공통 조상 알고리즘
\(\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에 게시됨