§ 15 클러스터 개관
21문제는 표면 도메인이 다르지만 (안테나, 택시, 단백질…), 풀이의 골격은 다섯 가지 패턴 중 하나다.
| 클러스터 | 핵심 패턴 | 대표 문제 | 공통 무기 |
|---|---|---|---|
| Load Balancing | PQ-Greedy + 주기 재조정 | BANK, IOT, 안테나, 택시 | 우선순위 큐, 잔량 제곱 패널티 |
| Spatial Opt. | 그리드 분할 + 중앙값 | 물류배송, 우주선, 쓰레기통, RTX5090 | k-d tree, Floyd-Warshall, integral |
| Graph & Flow | Dijkstra / Max-Flow | 대피소, 노후도로, 교차로 | 인접리스트, PQ, lazy deletion |
| Data Structure | 비트팩킹 + Radix Sort | 로봇청소기, 세균, 드론 | counting sort, 비트마스크, integral |
| Search & Est. | Bayesian / Tree Search | 죄인의숲, 어디있니, Square, 단백질 | 파티클, 엔트로피, integral image |
§ 2Cluster 1 — Load Balancing
패턴: 우선순위 큐 + 주기적 재조정
제한된 자원(화폐, 안테나 용량, 택시 가용)을 N개 요청자에게 나눠준다. “가장 고통받는 자가 먼저”가 황금 규칙. 우선순위 함수의 형태는 다르지만(잔량², 거리, α), 본질은 같다.
자원이 부족할 때 평균은 평등을 약속하지만 분산은 진실을 말한다. 분산이 줄어드는 방향으로 결정하면 거의 항상 옳다.
공통 트릭:
- 우선순위 함수에 제곱항 사용 → 큰 부족에 지수 패널티
- 주기적 재조정 (BANK: k%250, TV: 매 턴) → 누적 편향 제거
- lazy deletion으로 PQ 재구성 비용 회피
- k = √N 또는 N/4가 자주 sweet spot
§ 3Cluster 2 — Spatial Optimization
패턴: 공간 분할 + 거리 캐시
2D/3D 공간에서의 배치/경로/할당. 모든 쌍 거리를 미리 계산하거나 격자 분할로 인근 후보만 비교. O(N²) 사전계산이 O(N⁴) 무식한 검색을 이긴다.
공간 문제는 본질적으로 N²이지만, 인덱싱이 N log N으로 만든다. 무엇을 인덱싱할지가 알고리즘의 정체.
- Integral Image — 임의 사각형 합 O(1)
- Floyd-Warshall — 모든 쌍 최단거리 O(V³) 한 번
- k-d tree / quadtree — 영역 쿼리 O(log N)
- 맨해튼 → 체비셰프 좌표 회전으로 거리 단순화
§ 4Cluster 3 — Graph & Flow
패턴: Dijkstra / Max-Flow / Hungarian
노드-엣지 모델링이 가능한 문제. 의도된 정답은 Max-Flow 또는 Hungarian이지만 시간 부족. 작은 그래프(노드 수 < 100)에서는 Dijkstra-기반 휴리스틱이 95%로 흉내 낸다.
큰 그래프엔 Max-Flow, 작은 그래프엔 Dijkstra. 노드 수가 적을수록 단순한 방법이 의외로 정확하다.
- 3-노드 Dijkstra (대피소) — Hungarian의 95%
- 인접리스트 + PQ — O((V+E)log V)
- edge weight 동적 갱신 (lazy deletion + PQ rebuild)
- residual graph 없이도 PQ로 transshipment 흉내
§ 5Cluster 4 — Data Structure
패턴: 비트팩킹 + Radix Sort
대규모 데이터의 빠른 정렬·탐색. 표준 비교 정렬은 O(N log N)이지만 데이터 값 범위가 제한적이면 Counting Sort O(N) 또는 Radix Sort O(d·N)으로 가속.
값 범위가 작은 정렬은 비교가 아니라 카운팅이다. 이 사실 하나로 100배가 갈린다.
- 거리 + ID 비트팩킹: (dist << 8) | id — 한 번에 정렬 + 복원
- 비트마스크로 방문 상태 (DP, 부분집합)
- OR로 다중 영역 합산 (세균: 토너먼트 검사)
- Integral / Prefix sum 또는 Segment tree
§ 6Cluster 5 — Search & Estimation
패턴: 베이지안 / 엔트로피 / 패치 검색
불확실성 하의 탐색. 다중 가설을 유지하면서 매 단계 가장 정보량 큰 선택. 분포 자체를 추적하는 것이 점추정보다 강하다.
한 점 추정은 깨지기 쉽지만, 분포는 자연스럽게 회복된다. 정보이론이 알고리즘 설계의 컴퍼스다.
- 파티클 필터: 분포 = 가중 샘플
- Information Gain = 엔트로피 감소
- Multi-scale Integral Image: 패치 크기 무관 O(1)
- Branch & Bound: 가지치기 휴리스틱
§ 7알고리즘 분포 — 무엇이 자주 나오나
21문제에 등장한 알고리즘 빈도:
§ 84가지 메타패턴 — 묶음을 가로지르는 DNA
패턴 A — “사전계산 O(N²), 쿼리 O(1)”
Floyd-Warshall, Integral Image, 거리 캐시. 한 번 비싸게 만들면 영원히 싸다. 모든 효율적 알고리즘의 첫 번째 도구.
전처리는 비용이 아닌 투자다. 쿼리가 N²번 들어올 거라면 전처리 N²은 무료다.
패턴 B — “비교 정렬을 쓰지 마라, 비트로 정렬하라”
값 범위가 0~2³² 이내면 Radix Sort. 같은 셀에 여러 정보를 비트로 패킹(예: dist<<8 | id)하면 정렬 한 번이 그룹화까지 끝낸다.
비교 정렬은 N log N이지만 정보이론적 한계. 정보를 다른 형태로 비트에 우겨넣으면 그 한계를 우회한다.
패턴 C — “PQ + 주기적 rebuild”
동적 데이터에서 “당장 가장 급한 것”을 뽑는 일에 PQ는 완벽. 단, stale entry는 lazy하게 무시. 일정 주기로 전체 rebuild가 평균 비용을 낮춘다.
정확하기보다는 시기적절하라. 매번 완벽하게 PQ를 유지하는 비용이 stale 처리 비용보다 크다.
패턴 D — “점 대신 분포”
불확실성 하에선 단일 추정이 아닌 분포 유지. 파티클 필터, 베이지안 갱신, 엔트로피 기반 선택. 정보이론이 자연스레 들어옴.
최선의 추측은 평균이 아닌 사후분포다. 분포를 유지하는 알고리즘은 충격에 강하다.