Programming/알고리즘
트리 알고리즘 마스터 로드맵: LCA부터 HLD, ETT, LCT까지 완전 정복하는 순서 가이드
octo54
2025. 6. 10. 13:45
반응형
트리 알고리즘 마스터 로드맵: LCA부터 HLD, ETT, LCT까지 완전 정복하는 순서 가이드
알고리즘 공부에서 트리는 단골 주제입니다.
하지만 단순한 DFS/BFS 수준을 넘어서 경로 질의, 노드 업데이트, 동적 연결까지 다루려면
체계적인 학습 로드맵이 필요합니다.
이번 글에서는 기초부터 고급까지 트리 알고리즘을 마스터하는 로드맵을 제시합니다.
각 단계별로 학습 포인트, 추천 자료, 대표 문제도 함께 정리합니다.
🧱 1단계: 트리 기초 (DFS, 부모 저장, 깊이, 서브트리 크기)
주요 개념
- 트리는 사이클 없는 연결 그래프
- 루트 노드 기준 DFS 탐색
- 각 노드의 깊이(depth), 부모(parent), 자식 관계 등
실습 목표
- 서브트리 크기 계산
- 루트로부터 거리 계산
- 트리의 리프 노드, 중심 노드 찾기
추천 문제
⚙️ 2단계: LCA (Lowest Common Ancestor)
주요 알고리즘
- Binary Lifting
- Sparse Table
- DFS 시간표기법 + RMQ
학습 포인트
- LCA(u, v)는 경로 쿼리의 출발점
- Binary Lifting은 HLD/LCT에 필수 구성 요소
추천 문제
- BOJ 11437
- [Codeforces 1336B] – 쿼리마다 LCA + 거리 계산
🧭 3단계: Euler Tour Tree (ETT)
반응형
사용처
- 서브트리 쿼리
- 색칠 정보 관리
- 이진 세그먼트 트리와 결합하기 쉬움
학습 내용
- in[u], out[u] 인덱스 구성
- 세그먼트 트리 또는 BIT 연결
- Lazy Propagation 병행
추천 문제
- [AtCoder ABC 222E] – 서브트리 내 통계
- [BOJ 14267] – 회사 문화 1
🔀 4단계: Heavy-Light Decomposition (HLD)
사용처
- u–v 경로 합, 최댓값, 업데이트 등 고속 처리
- 정적 트리 기반 쿼리 최적화
학습 내용
- 체인 분할 (heavy / light)
- 경로 쿼리를 체인으로 분리 후 세그먼트 트리 적용
- Lazy Segment Tree 병행
추천 문제
- [BOJ 13510] – 트리와 쿼리 1
- [Library Contest Tree Query] – path update & query
🔁 5단계: Link/Cut Tree (LCT)
사용처
- 동적 트리: 간선 삽입/삭제, 경로 유지
- 동적 MST 유지
- Fully Dynamic Connectivity
학습 내용
- Splay Tree 기반 node rotation
- make_root, access, link, cut
- 경로 최댓값, 경로 합 augmentation
추천 문제
- [Codeforces 613E] – 동적 간선 삽입/삭제 + MST 유지
- [Yandex Cup] – 실시간 경로 최댓값 교체
🧠 비교 요약
알고리즘 정적/동적 경로 쿼리 서브트리 쿼리 난이도
| DFS 기초 | 정적 | ❌ | ❌ | 쉬움 |
| LCA | 정적 | 경로 구간 | ❌ | 보통 |
| ETT | 정적 | ❌ | ✅ | 쉬움 |
| HLD | 정적 | ✅ | ⚠️ 보완 필요 | 중간 |
| LCT | 동적 | ✅ | ⚠️ 어렵다 | 어려움 |
🎯 트리 마스터 플랜 요약
- DFS, 서브트리, 부모 저장 등 기초 완성
- Binary Lifting으로 LCA 완벽 이해
- ETT로 서브트리 색칠/통계 훈련
- HLD로 경로 합/최댓값 쿼리 마스터
- LCT로 동적 트리까지 커버
📘 추천 자료
- CP-Algorithms – 트리 알고리즘 시리즈
- USACO Guide – Gold 트리 쿼리
- AtCoder Library – ETT, HLD 구현
- TLE 알고리즘 유튜브 – LCT 구조 시각화
트리알고리즘, LCA, ETT, HLD, LCT, 알고리즘로드맵, 트리쿼리마스터, 경로질의, 서브트리, SEO 최적화 10개