§01은 데이터를 읽는 법, §02는 제약에서 분포를 추론하는 법, §03은 코드를 고치는 법이었다. 셋 다 일반 도구다. 그러나 시험장에서 마주치는 건 일반 문제가 아니라 구체적인 한 문제다. 이 페이지는 21문제를 다섯 클러스터로 묶고, 각 클러스터의 대표 문제에 분석 → 추론 → 개선 → 머리 재현의 4단계 훈련을 그대로 적용한다. 부류를 알아보는 눈, 그것이 §04의 결과물이다.
§01~§03을 끝낸 응시자는 "데이터를 읽고, 분포를 추론하고, 코드를 고칠 수 있다"고 믿는다. 맞다. 그러나 그 셋은 도구다 — 망치와 톱과 끌. 시험장에서 화면에 뜨는 건 도구가 아니라 완성해야 할 가구 하나다. 그리고 그 가구는 매번 새로운 것 같지만, 사실 다섯 종류뿐이다.
패턴 분석은 21문제를 다섯 클러스터로 분해했다. 표면 도메인은 안테나·택시·단백질·세균으로 다 다르지만, 풀이의 골격은 다섯 가지 중 하나다. 시험장에서 가장 빠른 응시자는 문제를 읽자마자 "이건 Load Balancing 부류군"이라고 부류를 짚는다. 부류가 잡히면 무기고가 자동으로 열린다 — Load Balancing이면 우선순위 큐, Spatial이면 격자 분할, Graph면 Dijkstra. 부류 식별은 알고리즘 선택의 90%를 30초에 끝낸다.
| 클러스터 | 핵심 패턴 | 대표 문제 (§04에서 다룸) | 가장 먼저 보는 것 |
|---|---|---|---|
| ① Load Balancing | PQ-그리디 + 주기 재조정 | 택시 배정, 안테나 배정 | "자원 vs 요청자" 구조 — 누가 부족한가 |
| ② Spatial Opt. | 격자 분할 + 거리 캐시 | 물류배송, 우주선 착륙, RTX5090 | 좌표 밀도 맵 — 군집인가 산포인가 |
| ③ Graph & Flow | Dijkstra / Max-Flow 흉내 | 노후화 도로, 대피소 | 노드–엣지로 모델링되는가 |
| ④ Data Structure | 비트팩킹 + Counting/Radix | 로봇청소기, 세균, 드론 | 값 범위가 좁은가 — 비교 정렬을 우회할 수 있나 |
| ⑤ Search & Est. | 베이지안 / 엔트로피 / 패치검색 | 죄인의 숲, 어디있니, Square | 불확실성이 있는가 — 점 추정인가 분포 추정인가 |
제한된 자원(택시, 안테나 용량, 화폐, 채널)을 N개의 요청자에게 나눠준다. 핵심 질문은 언제나 하나 — "누가 가장 고통받는가, 그에게 먼저 줘라". 대표 문제는 택시 배정과 안테나 배정이다. 둘 다 우선순위 큐(PQ) 그리디가 골격이고, 주기적 재조정이 마무리다.
문제 설명에 "한정된 X를 여러 Y에게 배정"이라는 골격이 보이면 Load Balancing이다. X는 택시·안테나·예산, Y는 승객·단말·요청. 이 구조가 보이는 즉시 무기를 꺼낸다 — 우선순위 큐, 잔량 제곱 패널티, 주기 재조정. 그리고 자문한다: "지금 가장 급한 한 명은 누구이며, 그를 어떤 숫자로 정렬할까?" 그 숫자가 우선순위 함수다.
택시 배정(deep-dive № 05)을 받았다고 하자. main.cpp를 열면 채점기가 택시·승객 좌표를 pseudo_rand()로 만든다. §01의 다섯 루틴을 이 순서로 적용한다.
// 채점기가 init에 택시·승객 배열을 넘긴다고 가정void init(Taxi taxis[], int taxiCnt, Passenger ps[], int psCnt) { // ① 승객 출발지가 평면 어디에 앉는가 — 군집? 산포? static int px[10000], py[10000]; for (int i = 0; i < psCnt; i++) { px[i] = ps[i].departure.x; py[i] = ps[i].departure.y; } density(px, py, psCnt, MAP_SIZE); // 루틴2 — 밀도 맵 distDist(px, py, psCnt); // 루틴3 — 쌍거리 분포 // ② 택시 분포도 같이 — 택시도 좌표를 가진다 static int tx[100], ty[100]; for (int i = 0; i < taxiCnt; i++) { tx[i] = taxis[i].pos.x; ty[i] = taxis[i].pos.y; } density(tx, ty, taxiCnt, MAP_SIZE); printf("taxi=%d passenger=%d ratio=%.1f\n", taxiCnt, psCnt, (double)psCnt / taxiCnt); fflush(stdout); return; // 분석만 — 확인 후 이 줄들을 주석 처리하고 풀이 작성}
ratio = 승객/택시가 100이면 택시 한 대가 평균 100명을 태운다는 뜻 — 한 번 배정으로 끝나는 게 아니라 반복 배정 문제임을 데이터가 말해준다.
§02의 PASS 역산 예제가 이미 택시 배정을 다뤘다 — MAP=10⁶, TC=5, CUT=432.5M, 승객 평균 7,500명. 역산하면 승객당 허용 비용 ≈ 11,533, 평균 쌍거리 50만의 1/43이다. §02의 판정은 명확했다: "가장 가까운 택시 배정이 필수, 무작위 배정은 즉사, swap 개선으로 마진 확보."
택시 100대 × 승객 1만 명. 만약 매 배정마다 "모든 택시 × 모든 승객"을 비교하면 O(10⁶)이고, 그걸 배정 횟수만큼 반복하면 폭발한다. §02의 N값 함의표가 가두는 결론: 승객 수 10⁴ → O(N·logN)이 한계다. 그러므로 우선순위 큐(삽입·추출 O(logN))가 자료구조로 강제된다 — 단순 배열 선형탐색은 등급 미달. 제약 추론이 "PQ를 써라"를 코드 짜기 전에 못박는다.
기본 해법(가장 가까운 택시 그리디)이 PASS 근처에 닿았다면, §03의 4단계로 끌어올린다.
// 개선 전: 거리만 본 그리디 — "가까운 택시에 붙인다"double costBasic(Taxi& t, Passenger& p) { return manhattan(t.pos, p.departure);}// 개선 후: 거리 + 택시 부하 불균형에 제곱 패널티double costTuned(Taxi& t, Passenger& p, double alpha) { double d = manhattan(t.pos, p.departure); double load = t.assignedCount; // 이 택시가 이미 맡은 수 return d + alpha * load * load; // ← 부하²: 쏠림에 지수 패널티}// §03 파라미터 스윕: alpha를 0, 10, 50, 100, 300으로 돌려// seed 100개 합산 점수가 최소가 되는 값을 고른다.
costBasic과 costTuned를 §03의 A/B 비교 하네스에 넣어 seed 1~100을 돌린다. alpha=0이면 둘은 같다 — 그것이 baseline. alpha를 키우면 거리가 조금 멀어도 한가한 택시로 분산되어, 전체 대기·이동 합이 줄어드는 구간이 나온다. 그 sweet spot을 파라미터 스윕으로 찾는다. 패턴 분석이 말한 "잔량 제곱 패널티"가 바로 이 alpha · load² 항이다.
k%250 재조정, № 16 TV 화질의 매 턴 재배분이 같은 원리다.
이제 IDE를 닫는다. 종이도 치운다. 눈을 감고 택시 배정 문제를 머릿속에서 처음부터 복기한다 — 이것이 실전 회로를 새기는 훈련이다.
0:00–0:30 부류 식별. "택시를 승객에게 배정 → 한정 자원 vs 다수 요청자 → Load Balancing." 무기고를 머릿속에 펼친다: PQ, 거리+부하² 비용, 주기 재조정.
0:30–1:30 분포 상상. 좌표는 % MAP_SIZE 균등 산포일 것이다(군집 코드가 없다면). density 맵은 고른 농담 — 그러므로 클러스터링 무의미, 거리 기반 그리디. ratio는 약 100 → 반복 배정.
1:30–2:30 등급 역산. CUT/승객 ≈ 1만, 평균거리 50만 → 1/43 → "정밀하게 풀어라". 무작위 금지, 가까운 택시 필수, swap 개선 필요.
2:30–4:00 설계. 택시별 부하를 PQ로 관리. 각 승객을 거리 + α·부하² 최소 택시에 배정. 250건마다 손해 큰 배정을 재조정. α는 스윕으로. — 머릿속에서 여기까지 막힘없이 흐르면, 이 부류는 정복된 것이다.
2D·3D 공간에서의 배치·경로·할당. 비용은 거의 항상 거리이고, 적은 거의 항상 O(N²)의 무식한 전수 비교다. 무기는 격자 분할, 거리 사전계산, Integral Image. 대표 문제는 물류배송, 우주선 착륙, RTX5090 칩 디자인이다.
문제에 x, y(또는 x, y, z) 좌표가 등장하고 "배치/경로/최단거리"를 묻는다면 Spatial이다. 가장 먼저 §01의 density()를 돌려 군집인가 산포인가를 30초에 답한다. 군집이면 분할정복·클러스터 배정, 산포면 전역 그리디·격자 인덱싱. 이 한 장의 밀도 맵이 알고리즘 대분류를 가른다.
물류배송(deep-dive № 03)은 센터 501~1000개, 주문 50만~100만 건이다. 주문이 100만 개라 §01 루틴을 그대로 쓰면 느리다 — 표본을 쓴다.
void analyzeLogistics(Order ord[], int ordCnt, Center ctr[], int ctrCnt) { // ① 주문 100만 — density는 전수 가능 (격자에 카운트만) static int ox[1000000], oy[1000000]; for (int i = 0; i < ordCnt; i++) { ox[i] = ord[i].x; oy[i] = ord[i].y; } density(ox, oy, ordCnt, MAP); // 주문 밀도 맵 // ② 센터도 같은 격자에 — 수요-공급 겹침을 본다 static int cx[1000], cy[1000]; for (int i = 0; i < ctrCnt; i++) { cx[i] = ctr[i].x; cy[i] = ctr[i].y; } density(cx, cy, ctrCnt, MAP); // 센터 밀도 맵 // ③ 주문 -> 가장 가까운 센터 거리 — 표본 4000개만 static int nd[4000]; for (int k = 0; k < 4000; k++) { int i = (k * 2654435761u) % ordCnt; // 의사난수 표본 int best = 1 << 30; for (int j = 0; j < ctrCnt; j++) { int d = abs(ox[i]-cx[j]) + abs(oy[i]-cy[j]); if (d < best) best = d; } nd[k] = best; } histogram(nd, 4000, "order->nearest center");}
§02의 물류배송 예제 그대로다. N값 함의: 주문 100만 → O(N²) 절대 금지, O(N·logN) 한계, O(N) 안전. 그러므로 "주문끼리 다 비교"는 시작도 불가 — 주문 각각을 가장 가까운 센터에만 붙이는 게 골격이다. 센터는 고작 1000개라, 주문 하나당 센터 1000개 스캔은 O(주문수 × 1000) = 10⁹ — 빠듯하다.
패턴 분석의 한 문장 — "공간 문제는 본질적으로 N²이지만, 인덱싱이 N log N으로 만든다. 무엇을 인덱싱할지가 알고리즘의 정체." 물류배송에서 인덱싱 대상은 센터다. 센터 1000개를 격자(grid bucket) 또는 k-d tree에 넣으면, 주문 하나가 자기 근처 버킷의 센터만 보면 된다 — O(주문수 × 1000)이 O(주문수 × 상수)로 떨어진다. 머리 재현 때 항상 자문하라: "더 작은 쪽 집합을 인덱싱했는가?"
물류배송의 베스트 해법은 "주문→가까운 센터 배정 + 센터별 NN 경로". §03 파라미터 스윕의 대상은 센터 선택 임계값(TH)이다.
// 가장 가까운 센터가 TH보다 멀면, 두 번째 센터와 부하 비교 후 선택int pickCenter(Order& o, Center ctr[], int n, int TH) { int b1 = -1, b2 = -1, d1 = 1<<30, d2 = 1<<30; for (int j = 0; j < n; j++) { int d = manhattan(o, ctr[j]); if (d < d1) { d2=d1; b2=b1; d1=d; b1=j; } else if (d < d2) { d2=d; b2=j; } } // 최근접이 TH 이내면 그냥 그것. 멀면 부하 적은 쪽으로. if (d1 <= TH) return b1; return (ctr[b1].load <= ctr[b2].load) ? b1 : b2;}// §03 sweep: TH = 500, 1000, 2000, 4000, 8000 으로 돌려// seed 1..100 합산 거리가 최소인 TH를 채택. 보통 곡선이 U자.
pickCenter의 for (j < n)가 주문 100만 번 호출되면 10⁹회, 그 자체가 시간의 90%를 먹는다. 그러면 스윕 이전에 센터 격자 인덱싱으로 n 스캔을 줄이는 게 우선이다. 병목을 안 고치고 TH만 스윕하면 1초 걸리는 코드를 0.99초로 만들 뿐이다. §03의 순서를 지켜라: 병목 → 스윕 → A/B.
물류배송으로 4단계를 한 번 돌렸으면, 같은 부류의 다른 문제로 부류 감각을 굳힌다. 도구 없이 머릿속으로만.
deep-dive № 08 우주선 착륙은 "넓은 지형에서 착륙 가능한 평탄한 사각 영역을 찾는" 문제다. 머리 재현: 부류 식별 — 격자 + 영역 합 → Spatial. 무기 호출 — "임의 사각형의 합을 O(1)로 묻는다 → Integral Image(2D 누적합)." 머릿속에서 누적합 점화식 S[y][x] = grid[y][x] + S[y-1][x] + S[y][x-1] - S[y-1][x-1]을 한 번 써본다. 이게 막힘없이 떠오르면 우주선 착륙은 손에 잡힌 것이다.
deep-dive № 13 RTX5090 칩 디자인도 같은 부류다 — 칩 위에 모듈을 배치하며 면적·거리 비용을 최소화. 머리 재현: "배치 + 거리 비용 → Spatial. 모든 쌍 거리를 미리 계산할까(O(N²) 사전계산), 격자로 인근만 볼까?" §02의 N값으로 어느 쪽인지 판정한다.
문제를 노드–엣지 그래프로 다시 그릴 수 있으면 Graph & Flow 부류다. 의도된 정답은 종종 Max-Flow나 Hungarian이지만 시험장에선 시간이 부족하다 — 작은 그래프에서는 Dijkstra 기반 휴리스틱이 95%로 흉내 낸다. 대표 문제는 노후화 도로와 대피소다.
문제에 "지점들 사이를 연결", "경로", "도달 비용", "수송/배분 네트워크"가 보이면 Graph다. 가장 먼저 할 일은 코드가 아니라 종이(또는 머릿속)에 노드와 엣지를 그리는 것. 노드는 무엇인가(교차로? 도로? 대피소?), 엣지의 가중치는 무엇인가(거리? 용량? 비용?). 그림이 그려지면 무기가 정해진다 — 최단경로면 Dijkstra, 매칭이면 Hungarian, 수송량이면 Max-Flow.
노후화 도로(deep-dive № 12)는 도로망의 상태값을 다룬다. Graph 문제에서 §01 루틴은 좌표가 아니라 그래프 자체의 형태를 본다 — 노드 수, 엣지 수, 가중치 분포.
void analyzeGraph(int nodeCnt, Edge edges[], int edgeCnt) { // ① 노드 차수 분포 — 그래프가 성긴가 빽빽한가 static int deg[10000] = {0}; for (int i = 0; i < edgeCnt; i++) { deg[edges[i].u]++; deg[edges[i].v]++; } histogram(deg, nodeCnt, "node degree"); // ② 엣지 가중치(도로 상태) 분포 — § 01 루틴1 그대로 static int w[100000]; for (int i = 0; i < edgeCnt; i++) w[i] = edges[i].cost; histogram(w, edgeCnt, "edge weight"); // ③ 밀도 비율 — E / (V·(V-1)/2). 1에 가까우면 완전그래프 double dense = (double)edgeCnt / (nodeCnt*(nodeCnt-1)/2.0); printf("V=%d E=%d density=%.3f\n", nodeCnt, edgeCnt, dense); fflush(stdout);}
O((V+E)logV)). density가 1에 가까우면 빽빽 — 인접행렬도 감당되고, V가 작으면 Floyd-Warshall(O(V³))이 오히려 단순하다. 엣지 가중치 히스토그램은 "도로 상태"가 균등인지 편향인지를 드러내 — 편향이 곧 공략점이다.
Graph 문제에서 §02의 N값 함의표는 노드 수 V를 본다. 패턴 분석의 핵심 통찰: "큰 그래프엔 Max-Flow, 작은 그래프엔 Dijkstra. 노드 수가 적을수록 단순한 방법이 의외로 정확하다."
V ≤ 100이면 — Floyd-Warshall(O(V³)=10⁶)이 즉시 가능하고, 모든 쌍 최단거리를 한 번에 캐시한 뒤 쿼리는 O(1). 백트래킹·완전탐색도 부분적으로 열린다. V ≤ 10⁴이면 — Floyd는 죽고(10¹²), Dijkstra(O((V+E)logV))가 한계. V ≥ 10⁵이면 — Dijkstra도 여러 번 돌리면 빠듯, 시작점 몇 개만. 대피소가 노드 수십 개의 작은 그래프라면 "3-노드 Dijkstra가 Hungarian의 95%"라는 패턴 분석의 인용이 그대로 적용된다.
Graph 부류의 §03 개선은 두 갈래다 — 자료구조 교체(인접행렬→인접리스트+PQ)와 lazy deletion으로 동적 갱신 비용 회피.
// 도로 상태가 갱신될 때마다 PQ를 통째로 재구성하면 비싸다.// 개선: 옛 항목은 버리지 않고, 꺼낼 때 stale이면 무시한다.void dijkstra(int src, int dist[], int ver[]) { priority_queue<Node> pq; // (dist, node, stamp) dist[src] = 0; pq.push({0, src, ver[src]}); while (!pq.empty()) { Node cur = pq.top(); pq.pop(); if (cur.stamp != ver[cur.node]) continue; // ← stale 무시 for (Edge& e : adj[cur.node]) { int nd = cur.dist + e.cost; if (nd < dist[e.to]) { dist[e.to] = nd; ver[e.to]++; // 버전 올림 → 옛 항목 stale화 pq.push({nd, e.to, ver[e.to]}); } } }}
O(logN)이 재구성 O(N)보다 압도적으로 싸다 — 패턴 분석의 메타패턴 C("PQ + 주기적 rebuild")이자 "정확하기보다는 시기적절하라"의 실체다. A/B 점수 차가 보이면 lazy를 채택한다.
deep-dive № 15 대피소는 "사람들을 대피소로 보내되 용량과 거리를 함께 고려"하는 문제다. 머리 재현: 그래프 그리기 — 출발지·중간지·대피소를 노드로, 이동거리를 엣지로. 등급 판정 — 노드가 수십 개로 작다 → Floyd 또는 반복 Dijkstra 가능. 의도된 정답 Max-Flow는 시간 부족. 설계 — "출발→중간→대피소"의 3단 경로를 Dijkstra로 풀면 Hungarian의 95%. 용량 초과는 lazy하게 다음 후보로 넘긴다. — 머릿속에서 노드–엣지 그림이 즉시 떠오르고 "작으니 Dijkstra로 충분"이라는 판단이 나오면, Graph 부류는 정복된 것이다.
대규모 데이터의 빠른 정렬·탐색·집계. 표준 비교 정렬은 O(N·logN)이지만, 값 범위가 제한적이면 Counting Sort O(N) 또는 Radix Sort로 가속한다. 무기는 비트팩킹, 비트마스크, Prefix sum / Integral. 대표 문제는 로봇청소기, 세균, 드론 배송이다.
문제에 "정렬", "그룹화", "영역 집계", "방문 상태 관리"가 보이고 데이터가 크다면 Data Structure 부류다. 가장 먼저 §01의 probe()로 값의 범위를 본다. 값이 0~수천 범위에 갇히면 — 비교 정렬을 버리고 Counting Sort. 여러 정보를 한 정수에 담아야 하면 — 비트팩킹(dist<<8 | id). 패턴 분석의 한 문장: "값 범위가 작은 정렬은 비교가 아니라 카운팅이다. 이 사실 하나로 100배가 갈린다."
로봇청소기(deep-dive № 01)는 64×64 격자, 셀 값 0·1·2, 먼지 100~399개. §02에서 이미 본 데이터다 — §01 루틴은 여기서 값의 좁음을 확인하는 데 쓴다.
void analyzeVacuum(int grid[][64], Dust dust[], int dustCnt) { // ① 먼지 좌표를 1D 키로 — y*64 + x, 범위 0~4095 static int key[400]; for (int i = 0; i < dustCnt; i++) key[i] = dust[i].y * 64 + dust[i].x; probe(key, dustCnt, 4095); // 정렬여부·중복·빈값 — 값 4096 범위 // ② 로봇-먼지 거리 분포 — 표본 불필요, 먼지 400개뿐 static int dx[400], dy[400]; for (int i = 0; i < dustCnt; i++) { dx[i] = dust[i].x; dy[i] = dust[i].y; } distDist(dx, dy, dustCnt); printf("dust=%d cell range=0..2 key range=0..4095\n", dustCnt); fflush(stdout);}
probe()가 "값 범위 0~4095"를 확인해주면 — 먼지 좌표를 정렬할 때 std::sort(O(N logN)) 대신 Counting Sort(O(N + 4096))가 가능하다는 신호다. 먼지가 400개뿐이라 정렬 비용은 어차피 작지만, 더 중요한 건 좌표를 1D 키로 압축할 수 있다는 발견 — y*64+x로 격자를 평탄화하면 비트팩킹·해싱·정렬이 전부 단순해진다. Data Structure 부류 분석의 핵심은 "어떤 압축이 가능한가"를 찾는 것.
§02의 로봇청소기 PASS 역산이 이미 답했다 — CUT=6.32M, TC 10, 먼지당 허용 이동 ≈ 2,528, 평균거리 42의 60배. 판정: "엄청나게 헐겁다, 단순 그리디로 충분, 정밀 TSP 불필요." Data Structure 부류에서 §02가 더 보는 것은 값 범위와 N의 곱이다.
Counting Sort는 O(N + V) — N은 원소 수, V는 값 범위. V가 N보다 지나치게 크면(예: 좌표 범위 10⁶인데 점은 1만 개) 카운팅 배열이 메모리·시간을 낭비한다. 그때는 좌표압축 후 카운팅, 또는 그냥 비교 정렬. "값 범위가 원소 수와 비슷하거나 작을 때만 카운팅이 이긴다" — 로봇청소기는 키 범위 4096, 먼지 400, 비율 10:1로 카운팅이 무난하다. §02의 N값 함의표를 "원소 수"와 "값 범위" 두 축으로 함께 읽어라.
Data Structure 부류의 §03 개선은 비트팩킹이 백미다 — 정렬 한 번으로 그룹화까지 끝낸다.
// 개선 전: (거리, id) 구조체 배열을 비교 정렬// 개선 후: 한 정수에 패킹 — 상위 24비트 거리, 하위 8비트 idvoid sortByDist(int dist[], int n, int outId[]) { static unsigned packed[100000]; for (int i = 0; i < n; i++) packed[i] = ((unsigned)dist[i] << 8) | (i & 0xFF); // packed를 정렬하면 거리 오름차순 + 같은 거리 안에서 id 순 radixSort(packed, n); // O(N) — 비교 정렬 아님 for (int i = 0; i < n; i++) outId[i] = packed[i] & 0xFF; // 하위 8비트 = 원래 id 복원}
dist를 상위 비트에 두면 정수 하나의 대소 비교가 곧 (거리, id) 사전식 비교가 되고, Radix Sort는 비교 없이 O(d·N). deep-dive № 06 세균의 블록 분할 탐색, № 09 드론 배송의 대규모 정렬이 모두 이 트릭으로 가속된다.
deep-dive № 06 세균은 격자 위 세균의 증식·검사를 다룬다. 머리 재현: 부류 식별 — 대규모 격자 + 영역 집계 → Data Structure. 무기 호출 — "여러 영역의 세균 유무를 한 번에 → 비트마스크 OR." 머릿속에서 떠올린다: 한 행을 64비트 정수로 보면, 영역 검사는 마스크 AND 한 번. 토너먼트식으로 OR을 누적하면 다중 영역이 O(영역수)가 아니라 워드 단위로 처리된다. 이 비트 회로가 머릿속에서 즉시 그려지면 세균은 손에 잡힌 것이다.
deep-dive № 09 드론 배송 머리 재현: "대규모 배송 정렬 → 값 범위 좁은가 → Counting/Radix → 좌표를 1D 키로 패킹." 로봇청소기에서 본 y*W+x 압축이 그대로 재등장한다 — 부류가 같으면 회로가 같다.
완전한 정보가 없는 상태에서의 탐색·추정. 다중 가설을 유지하면서 매 단계 가장 정보량이 큰 행동을 고른다. 무기는 파티클 필터, Information Gain(엔트로피 감소), Branch & Bound, Multi-scale Integral Image. 대표 문제는 죄인의 숲, 어디있니, Square다.
문제에 "숨어 있는 것을 찾아라", "위치를 추정하라", "질문/관측으로 좁혀가라", "최적 부분구조를 검색"이 보이면 Search & Estimation이다. 다른 네 부류와 결정적으로 다른 점 — 정답이 처음엔 안 보인다. 그래서 가장 먼저 자문한다: "한 점으로 추정할까, 분포로 추정할까?" 패턴 분석의 메타패턴 D — "점 대신 분포." 분포를 유지하면 충격에 강하다.
어디있니(deep-dive № 20)는 관측을 통해 자신의 위치를 추정하는 문제다. Search 부류에서 §01 루틴은 좌표가 아니라 관측의 정보량을 본다 — 한 번의 관측이 후보를 얼마나 줄이는가.
// 후보 위치의 분포를 belief[] 배열로 — 합이 1이 되는 확률void analyzeSearch(double belief[], int n) { // ① 엔트로피 — 불확실성의 크기. log2(n)이 최대(완전 무지) double H = 0; for (int i = 0; i < n; i++) if (belief[i] > 1e-12) H -= belief[i] * log2(belief[i]); // ② 최빈 후보의 확률 — 1에 가까우면 거의 확정 double peak = 0; int arg = 0; for (int i = 0; i < n; i++) if (belief[i] > peak) { peak = belief[i]; arg = i; } printf("entropy=%.2f / %.2f peak=%.3f at #%d\n", H, log2((double)n), peak, arg); fflush(stdout);}
peak 확률이 1에 가까워지는 순간이 "추정 완료" 신호다. §01의 히스토그램·요약 통계 대신, Search 부류는 엔트로피가 핵심 계측기다.
Search 부류에서 §02의 N값 함의표는 "몇 번의 관측·질문이 허용되는가"를 본다. 후보가 n개라면, 이상적으로 매 관측이 후보를 절반으로 줄일 때 log₂(n)번이면 확정 — 이것이 정보이론적 하한이다.
후보가 n개, 매 관측의 결과가 k가지로 갈린다면, 한 번의 관측이 줄일 수 있는 불확실성은 최대 log₂(k) 비트. 전체 불확실성 log₂(n) 비트를 없애려면 최소 log₂(n) / log₂(k)번의 관측이 필요하다. 예: 후보 1024개, 관측이 예/아니오 둘로 갈리면 log₂(1024)/log₂(2) = 10번이 하한. §02 식으로 채점기가 허용하는 관측 횟수와 이 하한을 비교하면 — 횟수가 넉넉하면 단순 전략으로 충분, 빠듯하면 매 관측마다 Information Gain을 최대화하는 정밀 전략이 필수.
Search 부류의 §03 개선은 관측 선택을 욕심내는 것 — 가능한 다음 관측 중 엔트로피를 가장 많이 줄이는 것을 고른다.
// 개선 전: 관측 지점을 순서대로 / 무작위로 고른다// 개선 후: 각 후보 관측의 기대 엔트로피 감소를 계산해 최대를 고른다int pickBestProbe(double belief[], int n, Probe probes[], int m) { double bestGain = -1; int best = 0; for (int p = 0; p < m; p++) { double H_after = 0; // 이 관측의 각 결과별 사후 엔트로피의 기댓값 for (int r = 0; r < probes[p].outcomes; r++) { double pr = probOfOutcome(belief, n, p, r); H_after += pr * entropyGivenOutcome(belief, n, p, r); } double gain = currentEntropy(belief, n) - H_after; if (gain > bestGain) { bestGain = gain; best = p; } } return best; // 가장 정보가 큰 관측}
deep-dive № 21 Square는 격자에서 특정 조건을 만족하는 정사각 패치를 찾는 문제다. 머리 재현: 부류 식별 — "조건 맞는 영역 검색 + 패치 크기가 여럿" → Search & Estimation의 패치 검색. 무기 호출 — "임의 크기 사각형의 합을 O(1)로 → Integral Image. 패치 크기가 여러 개면 → Multi-scale." 머릿속에서 떠올린다: 2D 누적합 한 장이면 어떤 크기의 정사각형 합도 모서리 네 값의 가감으로 즉시. 크기를 바꿔가며 Branch & Bound로 가지치기. 이 회로가 즉시 그려지면 Square는 정복된 것이다.
deep-dive № 18 죄인의 숲 머리 재현: "숨은 대상 추적 → 분포(파티클) 유지 → 매 단계 정보 최대 관측 → 가지치기." 어디있니에서 본 belief 추적이 그대로 재등장한다 — 부류가 같으면 회로가 같다.
§2~§6은 다섯 클러스터의 대표 문제 10개를 4단계로 훈련했다. 그러나 시험장에는 나머지 11문제도, 처음 보는 새 문제도 나온다. 새 문제를 만나도 당황하지 않으려면 — 21문제 전부가 이 다섯 안에 들어간다는 사실을 눈으로 확인해 두어야 한다. 아래 표가 그 지도다.
| № / 문제 | 클러스터 | 식별 신호 — "무엇이 보이면" | 대표 무기 |
|---|---|---|---|
| 01 로봇청소기 | ④ Data Structure | 좁은 격자 + 다수 먼지 순회 | NN 그리디 · 좌표 1D 키 |
| 02 안테나 배정 | ① Load Balancing | 한정 용량을 단말에 배정 | PQ · 용량 제약 필터 |
| 03 물류배송 | ② Spatial Opt. | 좌표 + 센터→주문 거리 최소화 | 격자 인덱싱 · NN 경로 |
| 04 IoT 가전 | ① Load Balancing | 제한 자원을 가전에 분배 | PQ-그리디 · 주기 재조정 |
| 05 택시 배정 | ① Load Balancing | 택시 vs 다수 승객 배정 | 거리+부하² · swap 개선 |
| 06 세균 | ④ Data Structure | 대규모 격자 영역 집계 | 비트마스크 OR · 블록 분할 |
| 07 교차로 신호제어 | ① Load Balancing | 신호 시간을 방향에 배분 | 시간축 PQ · 재조정 |
| 08 우주선 착륙 | ② Spatial Opt. | 지형에서 평탄 사각영역 탐색 | Integral Image |
| 09 드론 배송 | ④ Data Structure | 대규모 배송 정렬·스케줄 | Radix Sort · 비트팩킹 |
| 10 원형 화물배치 | ② Spatial Opt. | 무게·공간 배치 최적화 | 정렬 그리디 · 균형 분할 |
| 11 단백질 폴딩 | ⑤ Search & Est. | 거대 상태공간 구조 탐색 | Branch & Bound · 휴리스틱 |
| 12 노후화 도로 | ③ Graph & Flow | 도로망 + 동적 가중치 | Dijkstra · lazy deletion |
| 13 RTX5090 칩 | ② Spatial Opt. | 칩 위 모듈 배치 + 거리 비용 | 거리 사전계산 · 격자 분할 |
| 14 배달기사 | ① Load Balancing | 배달 건을 기사에게 배분 | PQ-그리디 · 부하 균형 |
| 15 대피소 | ③ Graph & Flow | 인원→대피소 경로+용량 | 3-노드 Dijkstra |
| 16 TV 화질 | ① Load Balancing | 화질 자원을 매 턴 재배분 | PQ · 매 턴 재조정 |
| 17 BANK | ① Load Balancing | 화폐를 요청에 배분 | PQ · k%250 재조정 |
| 18 죄인의 숲 | ⑤ Search & Est. | 숨은 대상 추적 | 파티클 · 가지치기 |
| 19 쓰레기통 | ② Spatial Opt. | 수거 지점 배치 + 거리 | 격자 분할 · 중앙값 배치 |
| 20 어디있니 | ⑤ Search & Est. | 관측으로 위치 추정 | 파티클 필터 · 베이지안 |
| 21 Square | ⑤ Search & Est. | 조건 맞는 정사각 패치 검색 | Multi-scale Integral Image |
§2~§7은 클러스터별로 (1)~(4)를 따로 훈련했다. 마지막 절은 그 (4) 머리 재현만 모아 한 자리에서 다섯 부류를 연속으로 복기하는 종합 훈련이다. 시험장에서 당신에게 주어지는 건 한 문제뿐 — 그 한 문제를 보고 5초 안에 부류를 짚고, 그 부류의 회로를 머릿속에서 끝까지 돌리는 능력이 §04의 최종 목표다.
타이머를 5분으로 맞추고, 1분마다 한 부류씩 머릿속에서 복기한다. 코드도 종이도 없이, 오직 회로만.
0:00 Load Balancing. "자원 vs 요청자"를 떠올린다. 택시 배정을 머릿속에서 — density로 수급 불균형 확인 → PASS 역산으로 "정밀하게" 판정 → PQ + 거리+부하² → 주기 재조정. 막힘없이 흐르는가?
1:00 Spatial Optimization. "좌표 + 거리"를 떠올린다. 물류배송 — density로 군집/산포 → N값으로 사전계산 가능 여부 → 작은 쪽(센터) 인덱싱 → Integral Image가 필요한가? 흐르는가?
2:00 Graph & Flow. "노드 + 엣지"를 떠올린다. 노후화 도로 — 차수 분포로 성김/빽빽 → V값으로 Floyd vs Dijkstra → lazy deletion으로 동적 갱신. 노드–엣지 그림이 즉시 그려지는가?
3:00 Data Structure. "값 범위"를 떠올린다. 로봇청소기 — probe로 범위 확인 → 좁으면 Counting/Radix → 좌표 1D 키 압축 → 비트팩킹. 비교→카운팅 치환이 떠오르는가?
4:00 Search & Estimation. "불확실성"을 떠올린다. 어디있니 — belief 분포 → 엔트로피로 계측 → Information Gain 최대 관측 → Integral Image / B&B. 점이 아니라 분포를 들고 있는가?
시험이 시작되면 — ① 문제를 읽으며 식별 신호를 찾는다(§7 표) → ② 부류가 잡히면 무기고가 열린다(§2~§6의 "가장 먼저 보는 한 가지") → ③ §01·§02 도구로 가설을 확인한다(분석·추론) → ④ 기본 해법을 짜고 §03으로 개선한다 → ⑤ 막히면 그 부류의 머리 재현 회로를 떠올려 빠진 무기를 찾는다. 이 다섯 단계가 끊김 없이 흐르도록 8주를 쓴다. §04는 그 흐름의 뼈대이고, §05 스케줄이 8주를 날짜로 채운다.