§01은 printf로 데이터를 봤다. 그러나 진짜 빠른 응시자는 출력 한 줄을 찍기 전에 이미 분포를 안다. static const int N = 64, % MAP_SIZE, % 100 + 1 — 이 세 줄이 격자 크기, 좌표 범위, 무게 분포를 전부 확정한다. 데이터를 만드는 코드는 데이터의 명세서다. 이 페이지는 그 명세서를 읽고, 시험 시작 30초 안에 알고리즘 등급을 판정하는 추론 기술이다.
Expert 시험은 입력 파일을 주지 않는다. 대신 main.cpp 안의 채점기가 pseudo_rand()로 데이터를 생성한다. 그런데 생성 코드는 자유롭게 쓰여 있지 않다 — 거의 모든 값이 pseudo_rand() % N + K라는 한 줄짜리 공식으로 만들어진다. 그 공식의 N과 K를 읽으면, 시드를 한 번도 돌리지 않고도 그 변수의 범위·분포·평균·표준편차가 전부 확정된다.
이것이 §01과 §02의 결정적 차이다. §01은 데이터를 관측한다 — printf를 꽂고 출력 창을 본다. §02는 데이터를 연역한다 — 코드만 읽고 분포를 머릿속에 그린다. 관측은 정확하지만 느리고(컴파일·실행·읽기 30초~1분), 연역은 근사적이지만 즉각적이다(읽는 즉시). 시험장에서 둘 다 쓴다: 먼저 연역으로 30초 안에 알고리즘 대분류를 정하고, 그 다음 §01의 루틴으로 가설을 확인한다.
static const int N = 64; // ← 맵은 64x64 격자로 고정static const int TC = 10; // ← 테스트 케이스 10개static int grid[N][N]; // ← 4096칸. 전체 순회해도 4096번static void make_tc() { for (int y = 0; y < N; y++) for (int x = 0; x < N; x++) grid[y][x] = pseudo_rand() % 3; // ← 셀 값 0,1,2 균등 dust = pseudo_rand() % 300 + 100; // ← 먼지 100~399개}
% 3이라 0·1·2가 각 33%씩 균등하게 섞인다. 먼지 개수는 % 300 + 100이라 100~399 균등, 평균 약 250. TC는 10개. — 시드를 한 번도 안 돌렸지만 데이터의 모양이 이미 손에 잡힌다.
첫 번째 체크리스트는 make_tc()를 한 줄씩 훑으며 각 pseudo_rand() 표현식을 분포 명세로 번역하는 작업이다. 패턴은 네 가지뿐이고, 각각 읽는 법이 정해져 있다.
가장 흔한 형태. 값이 0부터 N-1까지 각 1/N 확률로 균등하게 나온다. 좌표(% MAP_SIZE), 인덱스(% cnt), 분류값(% 3)이 전부 이 꼴이다. 평균은 (N-1)/2, 표준편차는 N/√12 ≈ 0.289·N. 균등이라는 사실 자체가 중요하다 — "데이터가 어느 영역에 몰려 있을 것"이라는 가정을 금지한다.
% 100 + 1은 1~100, % 300 + 100은 100~399. + K는 분포의 모양은 그대로 두고 시작점만 옮긴다. 무게·비용·재고처럼 "0이 되면 안 되는 양"에 + 1이 붙는 게 전형. 범위 폭은 여전히 N, 평균은 K + (N-1)/2.
두 균등 난수의 합은 더 이상 균등이 아니다 — 가운데가 솟은 삼각형 분포가 된다. 셋 이상을 더하면 종 모양(정규 근사). 무게가 % 50 + % 50 같은 꼴이면 평균값 근처에 데이터가 몰려 있다는 뜻이고, 그건 정렬·중앙값 트릭의 공략점이 된다. +가 두 개 이상 보이면 균등 가정을 버려라.
좌표나 ID를 뽑은 뒤 do-while로 "이미 쓴 값이면 다시 뽑기"를 하는 코드. 결과는 여전히 거의 균등하지만 중복이 없다는 보장이 추가된다. 이게 보이면 "두 점이 같은 칸에 겹칠 일은 없다"는 전제를 풀이에 쓸 수 있다 — 충돌 처리 코드를 통째로 생략할 근거다.
static void make_tc() { centerCnt = pseudo_rand() % 500 + 501; // 패턴2: 501~1000 orderCnt = pseudo_rand() % 500000 + 500001; // 패턴2: 50만~100만 for (int i = 0; i < orderCnt; i++) { do { order[i].x = pseudo_rand() % MAP; // 패턴1+4: 균등, 중복없음 order[i].y = pseudo_rand() % MAP; } while (occupied(order[i].x, order[i].y)); order[i].stock = pseudo_rand() % 50 + pseudo_rand() % 50 + 2; // 패턴3: 삼각, 2~100, 평균~51 }}
% 100은 0~99, % 100 + 1은 1~100이다. + 1 하나로 "값이 0일 수 있는가"가 갈린다. 0이 가능하면 0 무게·0 비용·0 거리 같은 경계 케이스를 풀이에서 다뤄야 하고, + 1이 있으면 그 코드를 생략할 수 있다. 제약을 읽을 때 % 뒤의 상수만 보지 말고 + 뒤까지 반드시 읽어라.두 번째 체크리스트는 가장 강력하다. 데이터의 개수(맵 크기·원소 수)를 보면, 어떤 시간복잡도까지 허용되는지가 거의 자동으로 결정된다. 시험 채점기는 보통 한 TC당 수백 ms~수 초의 예산을 준다. 현대 CPU는 1초에 약 108~109회의 단순 연산을 처리한다 — 이 수치를 기준으로 N이 복잡도 상한을 가둔다.
| 데이터 개수 N | 허용 복잡도 | 가능한 알고리즘 | 대표 문제 |
|---|---|---|---|
N ≤ 100 | O(N³), O(2N) 부분 | 완전탐색, 플로이드–워셜, DP 전부, 백트래킹 | 드론 배치(N≈50) |
N ≤ 5,000 | O(N²), O(N²·logN) | 모든 쌍 비교, 삽입정렬, DP 2차원, 이중 그리디 | 로봇청소기(맵 4096칸) |
N ≤ 105 | O(N·logN), O(N√N) | 정렬+그리디, 이진탐색, 세그먼트 트리, 우선순위 큐 | 택시 배정(승객 ~1만) |
N ≤ 106 | O(N·logN) 빠듯, O(N) 안전 | 해시·카운팅 정렬, 투 포인터, 선형 스캔, BFS/DFS | 물류배송(주문 50만~100만) |
N ≥ 107 | O(N) 필수, 상수도 작게 | 한 번 스캔, 비트 연산, 캐시 친화적 순회만 | 대규모 스트림형 문제 |
O(N²) 모든 쌍 비교(1012회)는 절대 불가, O(N·logN)(약 2천만회)이 한계, O(N)이 안전. 그러므로 "주문을 정렬 후 그리디"는 가능하지만 "주문끼리 다 비교"는 시작도 하면 안 된다.
두 N이 흔히 동시에 등장한다. 맵 크기(MAP_SIZE)는 좌표가 사는 공간의 변, 원소 개수(orderCnt 등)는 그 공간에 놓인 점의 수. 복잡도를 가두는 건 원소 개수이지 맵 크기가 아니다. 택시의 MAP_SIZE=106는 좌표 범위일 뿐 — 승객이 1만 명이면 알고리즘은 O(승객수) 기준으로 짠다. 단 맵 크기는 배열 메모리를 결정한다: int grid[106][106]는 메모리 폭발이므로, 큰 맵에서는 격자 배열 대신 좌표 리스트로 다뤄야 한다.
O(N²) 알고리즘을 완성한 뒤 시간 초과를 보는 것이다. N을 먼저 읽으면 그 30분이 시작되기 전에 멈춘다. 표의 행을 고르는 데 5초, 그 5초가 30분을 산다.세 번째 체크리스트는 TC 상수다. 채점기는 한 시드에 대해 여러 테스트 케이스를 돌리고, 전체 TC의 합산 시간이 제한 안에 들어야 한다. TC가 몇 개냐가 "TC 하나에 쓸 수 있는 시간"을 직접 나눈다.
| TC 개수 | TC당 시간 예산(총 5초 가정) | 전략적 함의 |
|---|---|---|
TC ≤ 5 | 약 1초 / TC | TC당 무거운 연산 가능. 한 TC가 크고 복잡한 단일 인스턴스 — 정밀한 알고리즘을 써도 된다. 초기화 비용이 커도 5번이면 흡수된다. |
TC ≈ 20~30 | 약 150~250ms / TC | 중간. TC마다 가벼운 초기화 + 효율적 본체. 매 TC memset 같은 큰 배열 초기화가 누적되니 초기화 비용도 예산에 넣어라. |
TC ≥ 100 | 약 50ms 이하 / TC | 빡빡. TC당 알고리즘은 거의 O(N)~O(N·logN)만 허용. 전역 배열 재초기화도 부담 — 필요한 칸만 되돌리는 부분 초기화가 필요할 수 있다. |
int main() { long long totalScore = 0; for (int tc = 0; tc < TC; tc++) { // ← TC만큼 반복 make_tc(); // 데이터 생성 init(...); // user 초기화 — 매 TC 호출 while (remainTime()) process(...); // user 본체 — 매 TC 호출 totalScore += scoreOfThisTC(); // TC 점수 누적 } printf("SCORE: %lld\n", totalScore); // ← 최종 합산 점수}
main의 for (tc < TC)를 찾으면 TC 개수가 보인다. 중요한 건 init이 매 TC마다 호출된다는 점 — init 안에서 큰 배열을 memset하면 그 비용에 TC를 곱한 만큼이 든다. TC=100에 memset으로 106칸을 매번 0으로 채우면 108회 — 그 자체로 1초를 먹는다. TC가 많을수록 초기화를 가볍게 하라.
TC=5 — TC당 1초씩 넉넉하니 승객 1만 명에 대한 정밀한 매칭을 돌릴 여유가 있다. 로봇청소기는 TC=10 — 맵이 4096칸으로 작아 TC당 부담이 거의 없다. 물류배송은 TC가 적지만 한 TC의 주문이 100만 개라 TC 내부가 무겁다 — TC 개수가 적어도 인스턴스가 크면 빡빡할 수 있으니 TC 개수와 인스턴스 크기를 함께 봐야 한다.네 번째 체크리스트는 가장 정량적이다. 채점기는 보통 CUT(통과 기준 점수)을 코드 어딘가에 명시한다. 그 점수와 데이터 규모를 결합하면, "한 단위 작업당 허용되는 평균 비용"을 역산할 수 있다. 그 허용 비용이 알고리즘 등급을 판정한다 — 그리디로 충분한가, 정밀 최적화가 필요한가.
CUT, 처리할 단위 개수 K(주문 수·승객 수·청소 칸 수 등)허용 평균 비용 = CUT / K필요 단위 처리율 = CUT / (전체 가능 단위)단위당 허용 연산 = T · 10⁸ / KTC당 ≈ 632,000.먼지당 허용 이동 = 632,000 / 250 ≈ 2,528.2·63 = 126. 평균 쌍거리는 약 42.TC당 ≈ 86.5M. 승객 평균 7,500명이면 승객당 허용 ≈ 11,533.0.5·10⁶ ≈ 500,000.배송당 허용 ≈ 13,000.scoreOfThisTC()나 등급 판정 if문을 읽어라 — 거기 숫자가 박혀 있다.네 체크리스트의 바탕에는 한 가지 수학적 사실이 있다 — pseudo_rand() % N은 이산 균등 분포를 만든다. 이 분포의 성질을 외우면, 제약을 보는 즉시 평균·표준편차를 암산할 수 있다.
X = pseudo_rand() % N이 0~N-1을 각 1/N로 균등하게 가질 때:
% 300 + 100 → 범위 300, σ ≈ 300/3.464 ≈ 87, 평균 ≈ 250summary() 루틴이 출력한 sd 값과 이 이론값을 비교하면, 데이터가 정말 균등인지 검증된다. 실측 σ가 이론 σ와 맞으면 균등 확정, 작으면 값이 뭉친 것(합 분포·필터링 의심).
X, Y ~ U[0, N)이 독립일 때 S = X + Y의 분포를 보자. 합이 s가 되는 (x, y) 쌍의 수는 x + y = s를 만족하는 격자점 수다. s가 0이나 2(N-1)에 가까우면 그런 쌍이 적고(모서리), s ≈ N-1이면 가장 많다(대각선이 가장 김). 그래서 가능한 쌍의 수가 가운데에서 최대인 삼각형 분포가 된다. 셋을 더하면(중심극한정리의 맛보기) 종 모양으로 매끄러워진다. — 그러므로 제약에서 +가 두 개 이상 보이면 "가운데에 몰린 데이터"를 예상하고, 그 가운데값 근처를 공략하는 정렬·중앙값 전략을 준비하라.
do { v = rand() % N; } while (used[v]);로 K개를 뽑으면, 분포는 여전히 거의 균등하지만 비복원 추출이 된다. K가 N에 비해 작으면(K ≪ N) 균등 가정 그대로 써도 되고, K가 N에 근접하면(예: N칸에서 0.9N개를 뽑음) 후반부 추출이 점점 "남은 칸"으로 몰려 약간의 편향이 생긴다. 대부분의 Expert 문제는 K ≪ N이라 균등으로 다뤄도 안전하다 — 단 "두 점이 절대 겹치지 않는다"는 보장은 확실히 챙겨라.시험이 시작되면 main.cpp가 화면에 뜬다. 코드를 풀이하기 전, 30초 동안 이 표 순서대로 훑는다. 각 칸의 답을 종이나 주석에 한 줄로 적어두면, 그 다섯 줄이 알고리즘 설계의 골격이 된다.
| 초 | 찾을 것 | 코드에서 보는 위치 | 적어둘 결론 |
|---|---|---|---|
0–5s | 가장 큰 N | static const int, 전역 배열 크기, cnt 변수의 % 범위 | "N ≈ ___ → 허용 복잡도 ___" |
5–10s | TC 개수 | main의 for (tc < TC) | "TC ___개 → TC당 ___예산" |
10–20s | 각 변수 분포 | make_tc()의 모든 pseudo_rand() % … + … | "좌표 균등 / 무게 삼각 / 중복없음 ___" |
20–25s | CUT 점수 | scoreOfThisTC, 등급 판정 if, CUT 상수 | "CUT ___ → 단위당 허용 ___" |
25–30s | 한 줄 판정 | 위 네 줄을 종합 | "이 문제는 ___형 + ___알고리즘 등급" |
do-while 안의 숨은 필터, if로 갈라지는 조건부 생성, 좌표를 군집 중심 주변에 뿌리는 코드 — 이런 것은 추론만으로 놓칠 수 있다. 그래서 30초 추론 뒤에는 반드시 §01의 분석 루틴(histogram, density)을 한 번 돌려 가설을 확인한다. 추론으로 시작하고, 관측으로 확정한다.