§ 13가지 메가트렌드
출제는 산업의 그림자다. 최근 21문제를 보면 세 가지 흐름이 뚜렷하다.
Trend ① — 정적 → 동적
기존 문제는 “주어진 입력에 한 번 답하라”. 신규 문제는 매 턴 상태가 바뀐다. 안테나(이동 UE), TV화질(사용자 분포 변화), 드론(스택 변화). 매 턴 재계산 비용이 새로운 제약.
Trend ② — 단일 → 다중 에이전트
로봇청소기 1대 → 다중 로봇 협업. 택시 1대 → 다중 차량 라우팅. 게임이론, 분산 최적화가 필요해진다.
Trend ③ — 확정 → 확률
노이즈 있는 센서, 무작위 사용자 행동, 불확실한 미래. 베이지안 / 파티클 필터 / 강화학습이 필수가 된다. 죄인의 숲, TV화질이 그 전조.
§ 29개 예상 문제군
P1 — 동적 라우팅 (Dynamic TSP / VRP)
매 턴 새 주문이 들어오고, 기존 경로를 재구성해야 한다. 정적 TSP를 풀 수 있어도 동적은 다른 문제.
왜 가능성 높은가: 우버, 쿠팡 등 실시간 라우팅이 산업 표준. 기존 “물류배송”의 자연스러운 확장. AHC(AtCoder Heuristic) 12번 “Capacitated VRP”와 유사.
P2 — 동적 자원 할당 (Online Bin Packing)
실시간으로 들어오는 요청을 “돌릴 수 없는” 결정으로 할당. 미래를 모른 채 후회를 최소화한다.
왜 가능성 높은가: 클라우드 컴퓨팅, 메모리 할당의 핵심. BANK(오프라인)의 온라인 버전. Competitive Ratio가 평가 척도가 될 수 있음.
P3 — 다중 에이전트 협력 (Multi-Agent Pathfinding)
N개의 로봇이 충돌 없이 동시에 목표 지점으로. 단일 A*의 N배가 아닌, 충돌 회피 + 협상 + 분산 결정.
왜 가능성 높은가: 창고 자동화(Amazon Kiva), 자율주행 차량 군집. 단일 로봇청소기의 자연스러운 확장. 충돌 회피 = 시공간 제약 그래프.
P4 — 3D 기하학 + 회전 최적화
3D 공간에 객체를 배치, 단 회전 자유도 포함. 단백질 폴딩은 회전이 결합 자유도, 새 문제는 6 DOF(병진+회전).
왜 가능성 높은가: 적층 인쇄, 컨테이너 적재, 우주 도킹. 회전 매트릭스 + AABB 검사 + 충돌 감지.
P5 — 대규모 그래프 (10⁶ 노드)
10⁶ 노드 + 10⁷ 엣지에서 최단경로/매칭. 메모리 자체가 도전.
왜 가능성 높은가: 소셜 네트워크, IoT 메쉬. 비트팩킹 + CSR 인접 표현 + 외부 메모리 알고리즘.
P6 — 실시간 스케줄링 (Online Job Scheduling)
작업이 시간에 따라 도착, 마감 + 우선순위 + 자원 제약. EDF(Earliest Deadline First)부터 시작.
왜 가능성 높은가: OS 스케줄러, 클라우드 컨테이너 오케스트레이션. 동적 PQ + 마감 추적.
P7 — 압축 / 인코딩 최적화
주어진 데이터를 비손실 압축. 사전 기반 vs 통계 기반 vs 변환 기반. 정보이론의 직접적 적용.
왜 가능성 높은가: 빅데이터 시대의 영원한 주제. 어디있니(엔트로피)와 유사한 정보이론 결합.
P8 — 동적 네트워크 플로우 (Time-Expanded Graph)
엣지 용량이 시간에 따라 변하는 그래프에서 최대 유량. 시공간 그래프로 변환.
왜 가능성 높은가: 교통망, 통신망의 실시간 운영. 정적 max-flow를 시간 축으로 확장.
P9 — ML 결합 최적화 (Learning + Search)
선택의 결과로 모델을 학습, 학습된 모델이 다음 선택을 가이드. Multi-armed bandit, contextual bandit, Q-learning의 알고리즘 대회 변형.
왜 가능성 높은가: 게임 AI, 추천 시스템, 자율주행. C++로 가벼운 ML 추론을 직접 구현해야 하는 새 영역.
§ 3필수 고난도 알고리즘 16선
예상 문제군에서 반복 등장할 고난도 알고리즘. High는 이번 회 이상 필수, Medium은 부분 등장, Low는 한두 문제에서 결정타.
| 알고리즘 | 핵심 아이디어 | 등장 문제군 | 우선순위 |
|---|---|---|---|
| Conflict-Based Search | 다중 에이전트 경로의 충돌 해결을 트리로 | P3 | HIGH |
| ALNS | 큰 이웃을 제거-재삽입으로 교란 | P1, P6 | HIGH |
| Min-Cost Max-Flow | 유량과 비용을 동시에 최적화 | P8, P2 | HIGH |
| Successive Shortest Path | MCMF의 표준 구현. Bellman-Ford 기반 | P8 | HIGH |
| Contraction Hierarchy | 대규모 그래프 최단경로를 노드 수축으로 가속 | P5 | HIGH |
| UCB1 / Thompson | 탐험-이용 트레이드오프의 베이지안 해 | P9 | MED |
| MCTS (Monte Carlo Tree Search) | 탐색을 무작위 시뮬레이션으로 | P3, P9 | MED |
| Quaternion / Rotation Matrix | 3D 회전을 4원수로 표현, 짐벌락 회피 | P4 | MED |
| GJK Collision Detection | 볼록 다각형 충돌의 표준 | P4 | MED |
| Octree | 3D 공간 8분할로 O(log N) 영역 쿼리 | P4, P5 | MED |
| Suffix Array / BWT | 문자열 압축 + 부분문자열 검색의 표준 | P7 | MED |
| Arithmetic Coding | Huffman을 넘어선 분수 비트 인코딩 | P7 | LOW |
| Stochastic Gradient Descent | 온라인 학습의 기본. MAB와 결합 | P9 | LOW |
| Simulated Annealing | 국소 최적해 탈출. 온도 cooling | P1, P4 | LOW |
| Lagrangian Relaxation | 제약을 비용으로 흡수해 풀기 쉬운 문제로 | P2, P8 | LOW |
| Augmenting Path | 이분 매칭의 표준. Hungarian의 기반 | P1, P2 | LOW |
§ 4학습 로드맵 — 12주 집중 플랜
Phase 1 (Week 1–3) — 기본기 강화
주제: Floyd-Warshall, Dijkstra, MCMF, Integral Image, Counting/Radix Sort, 비트 트릭
실전 문제: 기존 14문제 모두 시간 내 구현, 베스트 풀이 비교
핵심: 모든 표준 알고리즘 라이브러리 “30분 코드” 화
Phase 2 (Week 4–6) — 휴리스틱 + Local Search
주제: 2-opt, 3-opt, ALNS, Simulated Annealing, k-Median local search
실전 문제: 물류배송, 안테나, 대피소를 N=2x로 풀기. AHC 1–5번 답습
핵심: 시간 제약 하에서 점진적 개선 흐름 습득
Phase 3 (Week 7–9) — 확률 + 정보이론
주제: 파티클 필터, MAB, 엔트로피, MCTS, 베이지안 갱신
실전 문제: 죄인의 숲, 어디있니. AlphaGo 단순화판 구현
핵심: “불확실성 하 결정”을 코드로 표현하는 패턴
Phase 4 (Week 10–12) — 통합 + 모의고사
주제: 매주 4시간 풀-스택 모의고사. 신규 + 기존 혼합 출제
실전 문제: 본 페이지 P1–P9 시나리오 자작 + 풀이
핵심: 4시간 시간 분배, 우선순위 결정, 디버깅 속도