시험장에는 입력 파일이 없다. 인터넷도, 파이썬도, 엑셀도 없다. 그러나 당신 손에는 main.cpp가 있고, 그 안의 채점기가 pseudo_rand()로 데이터를 직접 만든다. 그 데이터는 메모리에 살아 있다. printf 한 줄이면 격자를 연다 — 이 페이지는 그 격자를 여는 다섯 개의 분석 루틴이다.
시험이 시작되면 화면에는 main.cpp 하나가 떠 있다. 입력 데이터는 보이지 않는다. 많은 응시자가 여기서 막연함에 빠진다 — "데이터를 모르는데 어떻게 분석하지?" 그러나 그 전제가 틀렸다.
Expert 채점기는 거의 예외 없이 다음 구조다. make_tc() 또는 run() 안에서 pseudo_rand() — 선형 합동 생성기(LCG) — 가 좌표·개수·무게 같은 모든 값을 만들어 전역 배열에 채운다. 시드는 보통 5로 고정돼 있다. 즉 데이터는 결정론적이고, 이미 메모리에 있다.
static unsigned long long seed = 5; // ← 고정 시드. 데이터는 결정론적static int pseudo_rand() { seed = seed * 25214903917ULL + 11ULL; return (seed >> 16) & 0x3fffffff;}static void make_tc() { driverCnt = pseudo_rand() % 50 + 51; // 51~100 passengerCnt = pseudo_rand() % 5000 + 5001; // 5001~10000 for (int i = 0; i < passengerCnt; i++) { passengerList[i].departure.y = pseudo_rand() % MAP_SIZE; passengerList[i].departure.x = pseudo_rand() % MAP_SIZE; // ... 데이터가 전역 배열에 살아서 채워진다 }}
make_tc()(또는 run()의 데이터 생성부)를 처음부터 끝까지 정독하는 것이다. % N의 N, + K의 K, 루프 범위, 중복 제거(do-while) 여부 — 이것이 데이터의 전부다. 코드가 곧 데이터 명세다.
init() 함수가 호출되는 시점에 데이터는 이미 완성되어 전역 배열에 들어 있다. 거기에 printf를 꽂으면 된다.분석 printf를 어디에 꽂느냐가 첫 결정이다. Expert 문제는 채점기가 user 함수(init, process, solve 등)를 호출하며 데이터 배열을 인자로 넘긴다. 두 가지 길이 있다.
채점기가 init(Coordinates antennas[])처럼 데이터를 넘겨준다면, init 첫 줄에 분석 루틴을 호출하고 return해 버린다. 채점기 본체(main.cpp)는 한 글자도 안 건드린다 — "main.cpp만 본다"는 제약과 충돌하지 않는다.
user 함수가 받는 인자만으로 부족하면, 채점기의 전역 배열을 extern 선언으로 끌어온다. 단 static 전역은 이 방법이 막힌다(파일 외부 비공개). 그때는 방법 A로 받은 인자만 쓴다.
실전에서는 방법 A를 기본으로 한다. user 코드 맨 위에 분석 함수 하나를 두고, 정식 풀이를 짜기 전에 그 함수만 호출해 출력을 본 뒤, 분석이 끝나면 호출을 주석 처리한다.
// ── 분석 단계: 이 호출로 데이터를 먼저 본다 ──void init(Coordinates antennas[]) { analyze(antennas, ANTENNA_NUM); // ← §3~§7 루틴 호출 return; // 분석만 하고 즉시 종료}// 출력 창에서 분포를 확인한 뒤, analyze() 줄을 주석 처리하고// 진짜 풀이를 init() 안에 작성한다.
printf가 안 보이면 출력이 버퍼에 갇힌 것이다. 채점기 main에 보통 setbuf(stdout, NULL)이 있어 괜찮지만, 없거나 프로그램이 중간에 죽으면 출력이 유실된다. 분석 함수 끝에 fflush(stdout)를 한 줄 넣어라. Visual Studio에서는 출력 창이 아니라 콘솔 창에 printf가 뜬다 — Ctrl+F5(디버깅 없이 시작)로 실행하면 콘솔이 닫히지 않는다.가장 먼저 보는 것은 분포의 모양이다. 좌표가 균등한가, 한쪽에 쏠렸는가, 무게가 작은 값에 몰렸는가. 히스토그램은 1차원 값 배열을 구간으로 나눠 막대로 그린다. ASCII 막대면 출력 창에서 즉시 읽힌다.
// 값 배열 v[0..n)을 BINS개 구간으로 나눠 ASCII 히스토그램 출력void histogram(int* v, int n, const char* name) { const int BINS = 20; int lo = v[0], hi = v[0]; for (int i = 1; i < n; i++) { // min/max 먼저 if (v[i] < lo) lo = v[i]; if (v[i] > hi) hi = v[i]; } int cnt[BINS] = {0}; double span = (hi - lo) + 1e-9; // 0 나눗셈 방지 for (int i = 0; i < n; i++) { int b = (int)((v[i] - lo) / span * BINS); if (b >= BINS) b = BINS - 1; cnt[b]++; } int mx = 1; for (int b = 0; b < BINS; b++) if (cnt[b] > mx) mx = cnt[b]; printf("=== %s [%d..%d] n=%d ===\n", name, lo, hi, n); for (int b = 0; b < BINS; b++) { int bar = cnt[b] * 50 / mx; // 막대 길이 0~50 int rlo = lo + (int)(span * b / BINS); printf("%6d |", rlo); for (int k = 0; k < bar; k++) putchar('#'); printf(" %d\n", cnt[b]); }}
pseudo_rand() % N의 전형) — 풀이에서 특정 영역을 가정하면 안 된다. 한쪽으로 치우치면 편향이 있다는 뜻이고, 그 편향이 곧 공략점이다. 가운데가 솟으면 정규 비슷 — 합으로 만들어진 값(여러 rand의 합)일 가능성.
% 100 + 1), 원형화물의 무게(50:50 혼합 분포), 노후화도로의 도로 상태(% 300 + 100) — 모두 히스토그램이 분포의 모양을 즉시 드러낸다.좌표 데이터는 1D 히스토그램으로는 부족하다. (x, y) 점들이 평면에서 뭉치는지 흩어지는지가 풀이를 좌우한다 — 택시·물류·드론·안테나가 전부 좌표 문제다. 평면을 굵은 격자로 나눠 셀마다 점 개수를 세고, 개수를 문자 농담으로 찍는다.
// 좌표 (xs[i], ys[i]) i=0..n) 을 G×G 격자 밀도로 출력void density(int* xs, int* ys, int n, int mapSize) { const int G = 24; // 24×24 격자 int grid[G][G] = {{0}}; for (int i = 0; i < n; i++) { int gx = xs[i] * G / mapSize; int gy = ys[i] * G / mapSize; if (gx >= G) gx = G - 1; if (gy >= G) gy = G - 1; grid[gy][gx]++; } int mx = 1; for (int y = 0; y < G; y++) for (int x = 0; x < G; x++) if (grid[y][x] > mx) mx = grid[y][x]; const char* shade = " .:-=+*#%@"; // 농담 10단계 printf("=== density %dx%d n=%d max=%d ===\n", G, G, n, mx); for (int y = 0; y < G; y++) { for (int x = 0; x < G; x++) { int s = grid[y][x] * 9 / mx; putchar(shade[s]); putchar(shade[s]); // 2칸 = 정사각 비율 보정 } putchar('\n'); }}
좌표 문제의 비용은 거의 항상 거리다. 점들이 서로 얼마나 떨어져 있는지의 분포를 알면, PASS 점수까지의 거리감이 잡힌다. 모든 쌍은 O(n²)이라 표본을 쓴다 — 무작위 쌍 수천 개의 거리만 봐도 분포는 충분히 드러난다.
// 무작위 점쌍 SAMPLES개의 맨해튼 거리를 표본하여 히스토그램void distDist(int* xs, int* ys, int n) { const int SAMPLES = 4000; static int d[SAMPLES]; unsigned s = 12345; // 분석 전용 LCG (채점기와 무관) for (int k = 0; k < SAMPLES; k++) { s = s * 1103515245u + 12345u; int i = (s >> 8) % n; s = s * 1103515245u + 12345u; int j = (s >> 8) % n; d[k] = abs(xs[i]-xs[j]) + abs(ys[i]-ys[j]); } histogram(d, SAMPLES, "pairwise distance"); // 루틴 1 재사용 long long sum = 0; for (int k = 0; k < SAMPLES; k++) sum += d[k]; printf("평균 쌍거리 ~ %lld\n", sum / SAMPLES);}
히스토그램이 그림이라면, 요약 통계는 숫자다. 최솟값·최댓값·평균·표준편차·중앙값 — 다섯 숫자면 분포의 성격이 잡힌다. 특히 평균과 중앙값의 차이가 치우침(skew)을 드러내고, 표준편차가 퍼짐을 말한다.
// 값 배열의 min/max/mean/stdev/median을 한 줄로 출력void summary(int* v, int n, const char* name) { static int t[100000]; for (int i = 0; i < n; i++) t[i] = v[i]; // 삽입정렬 or std 없이 간단 정렬 — 중앙값용 for (int i = 1; i < n; i++) { int key = t[i], j = i - 1; while (j >= 0 && t[j] > key) { t[j+1] = t[j]; j--; } t[j+1] = key; } long long sum = 0; for (int i = 0; i < n; i++) sum += v[i]; double mean = (double)sum / n; double var = 0; for (int i = 0; i < n; i++) var += (v[i]-mean) * (v[i]-mean); double sd = sqrt(var / n); printf("%-16s min=%d max=%d mean=%.1f sd=%.1f median=%d\n", name, t[0], t[n-1], mean, sd, t[n/2]);}
mean ≈ median이고 sd가 범위의 약 29%(균등분포 이론값 = 범위/√12)이면 — 전형적 rand % N 균등 분포다. mean > median이면 큰 값 쪽 꼬리(우편향), 반대면 좌편향. sd가 작으면 값이 뭉쳐 있어 — 그 자체가 공략 포인트(예: 거의 같은 무게 → 정렬 트릭).
앞의 네 루틴이 "분포의 모양"을 봤다면, 마지막 루틴은 데이터에 숨은 구조가 있는지 찌른다. 정렬돼 있는가? 중복이 있는가? 특정 값이 특별한가? 인접한 값에 상관이 있는가? 이런 구조가 하나라도 있으면 — 그것이 곧 지름길이다.
// 정렬 여부 · 중복 · 값 범위의 빈칸 · 인접 상관을 탐침void probe(int* v, int n, int valMax) { int asc = 1, dsc = 1, dup = 0; for (int i = 1; i < n; i++) { if (v[i] < v[i-1]) asc = 0; if (v[i] > v[i-1]) dsc = 0; } // 값 출현 카운트 — 중복과 빈 값 탐지 static int seen[100001]; for (int i = 0; i <= valMax; i++) seen[i] = 0; for (int i = 0; i < n; i++) { if (seen[v[i]]) dup++; seen[v[i]]++; } int empty = 0; for (int i = 0; i <= valMax; i++) if (!seen[i]) empty++; printf("sorted: %s | dup: %d | unused values: %d/%d\n", asc ? "ASC" : dsc ? "DESC" : "no", dup, empty, valMax + 1);}
sorted: ASC면 정렬된 입력 — 이진 탐색·투 포인터가 공짜로 열린다. dup이 크면 값이 좁은 범위에 몰려 — counting/radix 정렬, 비둘기집이 유효. unused values가 많으면 값 공간이 희소 — 해시·좌표압축이 필요. 구조 하나가 한 알고리즘 등급을 줄인다.