§ 1오늘 밤 — 새벽까지의 4시간 압축 학습
새벽까지 가능한 학습은 “새 알고리즘 익히기”가 아니라 “이미 아는 것을 손이 기억하게”. 다음 4단계가 가장 효율적.
22:00–22:45
이 페이지의 코드 스니펫 12개를 한 번씩 손으로 따라치기. 보지 않고 30초 안에 빈 에디터에서 재현될 때까지. (특히 Dijkstra, Counting Sort, Integral Image 3개는 반드시.)
22:45–23:30
최근 3년 문제 (안테나, 택시, 드론, RTX5090) 다시 풀이 흐름만 머릿속 재생. 코드 안 짜고 “어떤 자료구조 → 어떤 정렬 → 어떤 그리디” 흐름을 1분 안에 말로 설명.
23:30–00:15
판단 트리 § 3을 외우기. 문제 유형별 첫 3분에 무엇을 결정할지. 실제 시험 첫 30분의 운명이 여기서 갈림.
00:15–01:00
자주 하는 실수 25 § 6 훑기. 그리고 잠. 새벽 코딩은 다음날 손가락에 안 남는다.
07:00 기상
5분만: 판단 트리 한 번 더 + 시간 분배표 한 번. 그게 전부.
WARNING. 새벽 3시까지 새 알고리즘 학습은 역효과. 이미 아는 것의 손가락 기억(muscle memory)에 집중하는 것이 점수 +10점. 잠 7시간은 절대 깎지 말 것.
§ 2시험 4시간 — 시간 분배표
시험 시간이 정확히 4시간이라 가정. 각 단계의 시간을 미리 정해 “이 시간이 되면 다음 단계로”를 강제.
0:00–0:15 (15분)
문제 정독 + 모델 분해. 입력/출력/제약/점수 함수를 노트에 손으로 쓴다. 절대 키보드 안 만짐. 이 15분이 가장 비싼 15분.
0:15–0:30 (15분)
알고리즘 선택 + main 입출력 골격. 판단 트리에 따라 알고리즘 2개 후보를 노트에 적고 그중 더 안전한 쪽 선택. main의 입출력 골격만 먼저 작성하고 컴파일.
0:30–1:30 (60분)
Baseline 구현 — 무조건 PASS는 못해도 컴파일은 되는 코드. 단순 그리디 또는 무작위 배정이라도 OK. 점수가 PENALTY가 아니라 “계산 가능한 수치”가 나오는 게 핵심.
1:30–2:00 (30분)
제출 가능 점수 확보. 그리디 휴리스틱 추가. 이 시점에서 PASS 또는 PASS의 80% 점수 달성 목표.
2:00–3:00 (60분)
최적화 라운드 1. 우선순위 함수 튜닝, 정렬 도입, 사전 계산. 매 30분마다 점수 측정하며 “개선 없으면 롤백”.
3:00–3:30 (30분)
최적화 라운드 2. 비트 트릭, Radix Sort, Integral Image 등 미세 가속. 위험한 큰 리팩토링 금지.
3:30–4:00 (30분)
마지막 30분은 절대 새 코드 쓰지 마라. 엣지 케이스 확인, 제출 형식 검증, 시드 변경 테스트. 이 단계에서 빠뜨린 검증 1개 = 0점.
RULE. 1:30에 baseline이 안 돼 있으면 즉시 그 알고리즘 포기하고 더 단순한 것으로 전환. 끝까지 우아한 정답 추구하다 0점 vs. 60% 점수 — 후자가 항상 이긴다.
§ 3알고리즘 판단 트리 — 첫 3분에 결정
문제 정독 후 다음 8개 질문을 1분 안에 던지고 알고리즘을 선택.
[Q1] 점수 = Σ 거리/비용 최소화인가?
├── 예 → [Q2]
└── 아니오 → [Q5]
[Q2] 객체 수 × 객체 수가 10⁸ 이하?
├── 예 → Floyd-Warshall 또는 모든 쌍 사전 계산 가능
│ → 그리디 + Local Search (1-swap, 2-opt)
└── 아니오 → 공간 분할 (grid/quadtree) → 인근 후보만 비교
[Q3] 객체에 용량/제약이 있는가?
├── 예 → PQ-Greedy (우선순위 큐 + 잔량² 패널티) + 주기적 재조정
└── 아니오 → 단순 그리디로 baseline, 후 2-opt
[Q4] 시간에 따라 상태가 변하는가?
├── 예 → 매 turn 재계산 + 변화 예측 (lookahead 0.05~0.10 가중치)
└── 아니오 → 한 번 계산 후 캐시
[Q5] 그래프 구조 + 최단/최대 흐름?
├── 노드 < 100 → Dijkstra (소규모는 Floyd 가능)
├── 노드 100~10⁴ → Dijkstra + PQ + 인접리스트
└── 노드 > 10⁴ → Bidirectional Dijkstra 또는 A*
[Q6] 매칭/배정 + 비용 최소?
├── 작은 N (≤ 100) → Hungarian or MCMF
└── 큰 N → PQ-Greedy + 1-swap (95% 근사로 만족)
[Q7] 불확실성/노이즈가 있는가?
├── 예 → 베이지안 / 파티클 필터 / 분포 추적
└── 아니오 → 점추정 OK
[Q8] 패치/사각형 합 반복 쿼리?
├── 예 → Integral Image (사전계산 O(N²), 쿼리 O(1))
└── 아니오 → 직접 계산 OK
HEURISTIC. 잘 모르겠으면 항상 "PQ-Greedy + 1-swap local search". 21문제 중 12문제가 이 패턴으로 80%+ 점수 가능.
§ 4코드 스니펫 12선 — 시험장 카피·페이스트
새벽에 손으로 한 번씩 따라쳐서 외우자. 시험장에서 5분 안에 복원 가능해야 한다.
1. Priority Queue (수동 heap)
2. Counting Sort
3. Radix Sort (24+8 packing)
4. Dijkstra (인접리스트 + PQ)
5. Floyd-Warshall
6. BFS / 0-1 BFS
7. Integral Image 2D
8. Union-Find (path compression + rank)
9. 비트마스크 DP
10. 2-opt swap
11. pseudo_rand (재현 가능 시드)
12. 측정 + 시간 제한 루프
1. Priority Queue (수동 heap)
언제: std::priority_queue 안 쓰고 싶을 때, decrease-key 필요할 때
// 최소 힙. cmp 역으로 두면 최대 힙
struct Heap {
int data[1<<20], sz = 0;
void push(int x){
data[sz++] = x;
for (int i = sz-1; i > 0; ){
int p = (i-1)/2;
if (data[p] > data[i]) { std::swap(data[p], data[i]); i = p; }
else break;
}
}
int pop(){
int r = data[0];
data[0] = data[--sz];
int i = 0;
while (1){
int l = 2*i+1, ri = 2*i+2, m = i;
if (l < sz && data[l] < data[m]) m = l;
if (ri < sz && data[ri] < data[m]) m = ri;
if (m == i) break;
std::swap(data[i], data[m]); i = m;
}
return r;
}
bool empty() { return sz == 0; }
};
2. Counting Sort — O(N + K)
언제: 값 범위 K가 작을 때 (≤ 2¹⁶). 정렬이 비교 정렬보다 5–10배 빠름
// arr[N] 정렬, 값 범위 [0, K)
void countingSort(int arr[], int N, int K) {
static int cnt[1<<17], tmp[1<<20];
for (int i = 0; i < K; ++i) cnt[i] = 0;
for (int i = 0; i < N; ++i) cnt[arr[i]]++;
for (int i = 1; i < K; ++i) cnt[i] += cnt[i-1];
for (int i = N-1; i >= 0; --i)
tmp[--cnt[arr[i]]] = arr[i];
for (int i = 0; i < N; ++i) arr[i] = tmp[i];
}
3. Radix Sort with Bit Packing
언제: 거리+ID 같은 페어 정렬. (dist << 8) | id 형태로 한 번에 정렬 + 인덱스 복원
// trr[i] = (dist[i] << 8) | i 형태로 packing 후
// dist는 0..2²⁴ 이내. 한 번에 정렬 + id 복원.
int trr[N], out[N], cnt[256];
void radix(int n) {
for (int sh = 0; sh < 32; sh += 8) {
for (int i = 0; i < 256; ++i) cnt[i] = 0;
for (int i = 0; i < n; ++i) cnt[(trr[i] >> sh) & 255]++;
for (int i = 1; i < 256; ++i) cnt[i] += cnt[i-1];
for (int i = n-1; i >= 0; --i)
out[--cnt[(trr[i] >> sh) & 255]] = trr[i];
std::swap(trr, out); // 또는 memcpy
}
}
// 사용 후: id = trr[i] & 255; dist = trr[i] >> 8;
4. Dijkstra (인접리스트 + std::priority_queue)
언제: 단일 소스 최단경로. 음수 가중치 없음
#include <queue>
#include <vector>
struct Edge { int to, w; };
std::vector<Edge> adj[N];
int dist[N];
void dijkstra(int src) {
std::fill(dist, dist+N, INT_MAX);
dist[src] = 0;
std::priority_queue<std::pair<int,int>,
std::vector<std::pair<int,int>>,
std::greater<>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // lazy delete
for (auto& e : adj[u]) {
int nd = d + e.w;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push({nd, e.to});
}
}
}
}
5. Floyd-Warshall — 모든 쌍 최단
언제: V ≤ 500. O(V³) 사전 계산 후 모든 쿼리 O(1)
int dist[V][V];
void floyd(int V) {
// 초기: 직접 엣지는 가중치, 자기 자신은 0, 나머지 INF
for (int k = 0; k < V; ++k)
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX
&& dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
6. BFS / 0-1 BFS
언제: 격자 최단거리. 0-1 BFS는 가중치가 0 또는 1만 있을 때 deque로 Dijkstra 대체
#include <deque>
#include <queue>
// 일반 BFS (격자)
int dist[N][N];
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
void bfs(int sr, int sc) {
std::queue<std::pair<int,int>> q;
q.push({sr, sc}); dist[sr][sc] = 0;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr<0||nr>=N||nc<0||nc>=N) continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
// 0-1 BFS: edge cost 0이면 push_front, 1이면 push_back
std::deque<int> dq;
dq.push_front(src);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
// cost 0인 이웃: push_front; cost 1인 이웃: push_back
}
7. Integral Image 2D
언제: 임의 사각형 합을 여러 번 쿼리. 사전 O(N²), 쿼리 O(1)
int img[N+1][N+1], II[N+1][N+1];
void buildII() {
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
II[i][j] = img[i][j]
+ II[i-1][j] + II[i][j-1]
- II[i-1][j-1];
}
// 사각형 (r1,c1)부터 (r2,c2)까지 합. 0-indexed inclusive.
int rectSum(int r1, int c1, int r2, int c2) {
return II[r2+1][c2+1] - II[r1][c2+1]
- II[r2+1][c1] + II[r1][c1];
}
8. Union-Find
언제: 연결 컴포넌트, 동치류, MST(Kruskal), 그룹화
int par[N], rnk[N];
void init(int n) {
for (int i = 0; i < n; ++i) { par[i] = i; rnk[i] = 0; }
}
int find(int x) {
while (par[x] != x) {
par[x] = par[par[x]]; // path halving
x = par[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (rnk[a] < rnk[b]) std::swap(a, b);
par[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
return true;
}
9. 비트마스크 DP (TSP 형태)
언제: 작은 집합 (N ≤ 20) 위 부분집합 DP. TSP, 부분집합 합 등
// dp[mask][last] = mask 방문한 상태에서 last가 현재 위치인 최소 비용
int dp[1 << 20][20];
int dist[20][20]; // 두 점 거리
int tsp(int N) {
int INF = 1e9;
for (int m = 0; m < (1 << N); ++m)
for (int i = 0; i < N; ++i) dp[m][i] = INF;
dp[1][0] = 0; // 0번에서 출발
for (int m = 1; m < (1 << N); ++m) {
for (int u = 0; u < N; ++u) {
if (!(m & (1 << u))) continue;
if (dp[m][u] == INF) continue;
for (int v = 0; v < N; ++v) {
if (m & (1 << v)) continue;
int nm = m | (1 << v);
int nd = dp[m][u] + dist[u][v];
if (nd < dp[nm][v]) dp[nm][v] = nd;
}
}
}
int ans = INF;
for (int u = 1; u < N; ++u)
ans = std::min(ans, dp[(1<<N)-1][u] + dist[u][0]);
return ans;
}
10. 2-opt swap (TSP local search)
언제: TSP, 라우팅 문제 baseline. 한 라운드 O(N²)
// route[N]: 현재 순서. 점수가 줄어드는 swap을 반복.
int route[N];
int totalCost(); // 현재 순서의 비용
bool twoOpt() {
bool improved = false;
for (int i = 0; i < N-2; ++i) {
for (int j = i+2; j < N; ++j) {
// route[i..i+1]과 route[j..j+1] 엣지를 끊고
// route[i..j]를 뒤집어 보기
int before = dist(route[i], route[i+1])
+ dist(route[j], route[(j+1)%N]);
int after = dist(route[i], route[j])
+ dist(route[i+1], route[(j+1)%N]);
if (after < before) {
std::reverse(route + i+1, route + j+1);
improved = true;
}
}
}
return improved;
}
// while (twoOpt()) {} ← 수렴까지 반복
11. pseudo_rand — 재현 가능 시드
언제: 시드 변경 테스트, 디버깅 재현성
// 출제용 표준 LCG. seed 같으면 출력 같음.
unsigned long long seed = 5;
int prand() {
seed = seed * 25214903917ULL + 11ULL;
return (seed >> 16) & 0x3fffffff;
}
// 0..N-1 사이 정수: prand() % N
// 0..1 사이 실수: prand() / (double)0x3fffffff
12. 측정 + 시간 제한 루프
언제: 시간 제한 안에서 반복 개선 (Local Search, Simulated Annealing)
#include <time.h>
double TIME_LIMIT = 2.8; // 초 (3초 제한에 0.2초 마진)
clock_t start = clock();
double elapsed() {
return (double)(clock() - start) / CLOCKS_PER_SEC;
}
// Local search loop
while (elapsed() < TIME_LIMIT) {
int iter = 0;
bool improved = twoOpt();
if (!improved) {
// 진동 탈출: 무작위 perturbation
randomShuffle();
}
iter++;
}
§ 5실전 패턴 4축 — 막힐 때 돌아갈 안전망
패턴 A — “PQ-Greedy + Stale skip”
자원 배정 + 우선순위. 매번 PQ에서 pop, 우선순위가 stale이면 다시 push하고 continue. 50% 문제가 이걸로 해결.
while (!pq.empty()) {
auto t = pq.top(); pq.pop();
if (t.prior != currentPrior(t.id)) {
t.prior = currentPrior(t.id);
pq.push(t); // stale: 재삽입 후 다시
continue;
}
process(t);
}
패턴 B — “사전계산 O(N²), 쿼리 O(1)”
거리, 합, 인접 정보. 무엇이든 N² 한 번 미리 만들어두면 모든 후속 결정이 빠르다. Floyd, Integral, 인접리스트.
// 시험 시작 후 10분 안에 만들어 둘 수 있는 것들:
// 1. 모든 쌍 거리: dist[i][j]
// 2. 누적합: II[i][j]
// 3. 각 점의 가장 가까운 k개 후보: nearest[i][k]
패턴 C — “두 번 호출하면 두 번째에 정보 추출”
init/scanUE/scan 등 같은 함수가 여러 번 호출되면, 첫 호출은 무지 상태로 conservative하게, 두 번째부터 첫 호출에서 얻은 정보 활용. (안테나, IOT 모두 이 패턴.)
static int callCnt = 0;
void scanUE(...) {
callCnt++;
if (callCnt == 1) {
// 보수적 — 모든 가능성 고려
for (...) range[i] += SAFETY_MARGIN;
} else {
// 첫 호출 정보 활용 — 방향, 패턴 추출
useFirstCallInfo();
}
}
패턴 D — “Baseline은 그리디, 개선은 Local Search”
완벽한 알고리즘 추구하지 말고, 그리디로 baseline 만들고 시간 남는 만큼 1-swap/2-opt로 개선. 5-근사 보장이지만 실전 1.05배.
solution = greedy(); // 30분
while (elapsed() < TIME_LIMIT) {
if (!oneSwap(solution)) break; // 더 개선 없으면 종료
}
§ 6자주 하는 실수 25
아는 거 안 빠뜨리는 게 모르는 거 새로 외우는 것보다 +20점.
| # | 실수 | 증상 | 예방 |
|---|---|---|---|
| 1 | 배열 크기 1 부족 | RTE / WA | N+5 만큼 항상 여유 |
| 2 | int overflow | 음수, 0 반환 | 곱셈/누적합엔 long long |
| 3 | memset 잘못된 값 | 0/0xFF만 안전 | 다른 값은 std::fill |
| 4 | 전역 vs 지역 배열 | 스택 폭발 | 큰 배열은 항상 전역 |
| 5 | scanf %d vs %lld | 입력 깨짐 | printf도 마찬가지로 매치 |
| 6 | endl vs "\n" | flush로 느려짐 | "\n" 사용 |
| 7 | cin/cout 동기화 | 입출력 느림 | sync_with_stdio(false) |
| 8 | vector push_back 폭발 | O(N²) reserve 부족 | reserve 미리 호출 |
| 9 | passing by value (큰 객체) | 복사 폭발 | const& 또는 * |
| 10 | std::map 사용 | O(N log N) 상수 큼 | unordered_map 또는 직접 hash |
| 11 | std::set 사용 | 같이 느림 | 정렬된 vector + 이진검색 |
| 12 | recursion 깊이 | stack overflow | iterative로 변환 또는 큰 stack |
| 13 | 방향 dy/dx 순서 | WA | {상,하,좌,우} 순으로 통일 |
| 14 | 경계 검사 누락 | RTE | 매 이동마다 if 검사 |
| 15 | %d로 long long | 이상한 값 | %lld |
| 16 | 비트 시프트 우선순위 | WA | 괄호 명시 |
| 17 | 0으로 나누기 | RTE | denominator 항상 검사 |
| 18 | 중첩 break 안 됨 | 로직 오류 | goto 또는 flag |
| 19 | compare 함수 strict 위반 | RTE on std::sort | < 만 사용, <= 금지 |
| 20 | shadowing 변수 | silent bug | 외부 변수 이름 다르게 |
| 21 | seed reset 누락 | TC마다 다른 결과 | 매 TC 시작 시 reset |
| 22 | global 상태 누락 | 다음 TC 영향 | 매 TC 시작 초기화 |
| 23 | 같은 PQ에 stale entry | 잘못된 선택 | pop 후 검증, lazy delete |
| 24 | floor/ceil 혼동 | off-by-one | 정수 나눗셈 명확히 |
| 25 | 점수 함수 잘못 계산 | 큰 차이 | main 점수 함수 다시 읽기 |
§ 7멘탈 + 마지막 체크
시험 시작 전 5분 루틴
- 물 한 잔, 화장실. 중간에 끊지 마라.
- 키보드 단축키 확인 (특히 컴파일·실행 단축키).
- 출력 디렉토리, 시드 입력 형식 확인.
- 모니터에 시계 또는 폰 타이머 4시간 세팅.
- 심호흡 30초. "천천히 정확하게가 빠르다"를 마음에.
막혔을 때 5분 리셋 프로토콜
- 코드를 일단 컴파일 가능한 상태로 만들고 그대로 둠.
- 일어나서 30초 스트레칭, 물 한 모금.
- 노트에 "지금까지 시도한 것"과 "다음 후보 3개" 적기.
- 가장 단순한 후보부터 시도. "마지막 30분에는 새 코드 금지".
제출 전 마지막 5분 체크리스트
- 여러 시드(예: 5, 100, 999)로 점수 측정. 한 시드만 좋은 건 우연.
- 출력 형식: 줄바꿈, 공백, 끝 newline 확인.
- 전역 변수가 매 TC 초기화되는지 확인.
- 시간 제한의 80% 안에 끝나는지 확인 (margin).
- 제출 파일 한 번 더 열어서 확인.
시험은 “최고의 알고리즘”이 아니라 “시간 안에 가장 많은 점수”다.
Baseline 80%와 우아한 0%면 80%가 항상 이긴다.
오늘 밤은 새 거 외우지 말고, 손이 기억하도록 따라치자. 잘 자.