토픽 91 / 92·비교표
구간 쿼리와 트리 자료구조
Sliding Window vs Prefix Sum vs Segment Tree
| 항목 | Sliding Window | Prefix Sum | Segment Tree |
|---|
| 시간 | O(N) | O(N) 전처리, O(1) 쿼리 | O(N) 전처리, O(log N) 쿼리 |
| 갱신 | 슬라이드 | O(N) (재계산) | O(log N) |
| 적용 | 연속 부분 배열 | 정적 구간합 | 동적 구간 쿼리 |
Two Pointers vs 이분 탐색 vs 해시
| 항목 | Two Pointers | 이분 탐색 | 해시 |
|---|
| 시간 | O(N) | O(N log N) | O(N) |
| 공간 | O(1) | O(1) | O(N) |
| 조건 | 정렬 필요 | 정렬 필요 | 없음 |
| 적용 | 합/구간 문제 | 범위 탐색 | 존재 확인 |
비트마스크 DP vs 완전탐색 vs 근사
| 항목 | 비트마스크 DP | 완전 탐색 | 근사 알고리즘 |
|---|
| 시간 | O(2^N * N) | O(N!) | 다항 시간 |
| 최적 | 보장 | 보장 | 근사 |
| N 제한 | 20 이하 | 10 이하 | 제한 없음 |
| 적용 | TSP (소규모) | 매우 소규모 | 대규모 TSP |
HLD vs Link-Cut Tree vs Euler Tour
| 항목 | HLD (Heavy-Light) | Link-Cut Tree | Euler Tour |
|---|
| 경로 쿼리 | O(log^2 N) | O(log N) | 서브트리만 |
| 동적 트리 | X | O (간선 추가/삭제) | X |
| 구현 | 중간 | 복잡 | 단순 |
| 적용 | 트리 경로 쿼리 | 동적 그래프 | 서브트리 쿼리 |