§02의 PASS 역산이 "얼마나 잘 풀어야 하는가"를 숫자로 못박았다. 그런데 첫 풀이를 돌렸더니 점수가 그 숫자에 못 미친다 — 시험장에서 가장 흔한 순간이다. 여기서 응시자는 두 갈래로 갈린다. 한쪽은 코드를 노려보며 "여기가 느린 것 같다"는 직감으로 손을 댄다. 다른 한쪽은 clock() 한 줄을 꽂아 어디가 느린지 보고, for 루프로 임계값을 훑어 최적값을 찾고, #if 스위치로 두 버전을 같은 시드에서 겨룬다. 인터넷도 프로파일러도 없지만 Visual Studio의 컴파일러와 printf만으로 충분하다. 이 페이지는 그 체계적 개선의 4단계 기법이다.
첫 풀이를 제출했더니 SCORE가 PASS CUT에 모자란다. 혹은 PASS는 했지만 시간이 빠듯해 다음 TC에서 터질 것 같다. 이때 시험장에 남은 시간은 보통 20~40분. 이 시간을 어떻게 쓰느냐가 합격과 불합격을 가른다 — 그리고 그 사용법에는 좋은 절차와 나쁜 절차가 분명히 있다.
나쁜 절차는 이렇게 흘러간다. 코드를 위에서 아래로 읽으며 "이 이중 루프가 의심스럽다"고 느낀다. 그 루프를 30분에 걸쳐 정교하게 고친다. 다시 돌려본다. 점수가 그대로다 — 그 루프는 애초에 병목이 아니었다. 남은 시간은 5분, 손을 댈 곳은 없다. 직감으로 고른 대상이 틀렸기 때문에 30분이 통째로 증발했다.
좋은 절차는 측정으로 시작한다. clock() 한 줄을 함수 앞뒤에 꽂아 어느 구간이 실제로 시간을 먹는지 본다. SCORE를 부분별로 분해해 어느 항목이 점수를 깎는지 본다. 그 측정이 가리키는 한 곳을 고치고, 다시 측정해 효과를 확인한다. 효과가 없으면 되돌리고 다음 후보로 간다. 이 사이클은 느려 보이지만 — 틀린 대상에 시간을 쓰지 않으므로 결국 가장 빠르다.
코드를 고치기 전에 반드시 두 가지 숫자를 손에 쥐어야 한다 — 시간 분해(어느 함수가 몇 ms를 먹는가)와 점수 분해(어느 항목이 SCORE를 얼마나 깎는가). 이 두 숫자 없이 코드를 고치는 것은 어둠 속에서 총을 쏘는 것이다. 맞을 수도 있지만, 맞았는지조차 알 수 없다. 측정은 30초~2분이면 끝나고, 그 2분이 30분의 헛수고를 막는다. 시험장에서 가장 비싼 자원은 시간이고, 측정은 그 시간을 가장 적게 쓰는 길이다.
이 페이지의 4단계 기법은 그 좋은 절차를 도구로 만든 것이다. 기법 ①은 병목을 찾는다 — 어디를 고칠지. 기법 ②는 파라미터를 훑는다 — 상수를 어떤 값으로 바꿀지. 기법 ③은 두 코드를 겨룬다 — 새 버전이 정말 나은지. 기법 ④는 이 셋을 사이클로 묶는다 — 측정→가설→수정→재측정의 점진 개선 루프. 네 기법 모두 인터넷·외부 프로파일러·파이썬 없이, Visual Studio의 컴파일러와 표준 라이브러리(<time.h>, <stdio.h>)만으로 돌아간다.
개선의 첫 단계는 대상을 특정하는 것이다. 시험장에는 프로파일러가 없지만, 프로파일러가 하는 일의 90%는 clock() 두 줄로 재현된다 — 구간의 시작과 끝에서 시각을 찍고, 그 차이를 누적한다. 이것을 구간 시간 측정(interval timing)이라 한다.
C 표준 라이브러리의 clock()은 프로그램이 소비한 CPU 시간을 clock_t 단위로 돌려준다. 두 시점의 clock() 값을 빼고 CLOCKS_PER_SEC으로 나누면 초 단위 경과 시간이 나온다. 이것을 측정하고 싶은 함수의 앞뒤에 꽂으면 그 함수가 먹는 시간이 보인다.
#include <time.h>#include <stdio.h>// 구간별 누적 시간을 담는 전역 — 라벨 인덱스로 접근static double g_acc[16] = {0}; // 구간별 누적 초static long long g_hits[16] = {0}; // 구간별 호출 횟수static clock_t g_t0[16]; // 구간별 진입 시각// 구간 id의 측정을 시작한다static inline void tic(int id) { g_t0[id] = clock(); }// 구간 id의 측정을 끝내고 누적한다static inline void toc(int id) { g_acc[id] += (double)(clock() - g_t0[id]) / CLOCKS_PER_SEC; g_hits[id] += 1;}// 전체 구간의 누적 시간을 표로 출력한다void timerReport(const char* labels[], int nLabel) { double total = 0; for (int i = 0; i < nLabel; i++) total += g_acc[i]; if (total < 1e-9) total = 1e-9; // 0 나눗셈 방지 printf("=== TIMER total=%.3fs ===\n", total); for (int i = 0; i < nLabel; i++) { double pct = g_acc[i] * 100.0 / total; printf("%-18s %8.3fs %5.1f%% x%lld\n", labels[i], g_acc[i], pct, g_hits[i]); } fflush(stdout);}
id(0, 1, 2 …)를 정하고, 그 구간의 시작에 tic(id), 끝에 toc(id)를 넣는다. 같은 id를 반복 호출하면 시간이 누적되므로, 루프 안에서 매번 호출되는 함수도 총 소비 시간을 잴 수 있다. 마지막 TC가 끝난 뒤 timerReport()를 한 번 부르면 구간별 시간·비율·호출 횟수가 표로 나온다.
이 타이머를 user 코드에 끼우는 방법은 §01에서 본 "방법 A"와 같다 — 채점기 main.cpp는 건드리지 않고, user 함수 안에서만 tic/toc를 부른다. 예를 들어 택시 배정 풀이가 "후보 생성 → 거리 계산 → 매칭 → 개선" 네 단계라면, 각 단계를 id 0~3으로 감싼다.
// 구간 id 정의 — 의미를 이름으로 박아둔다enum { T_BUILD, T_DIST, T_MATCH, T_IMPROVE };static const char* TLAB[] = { "build candidates", "distance calc", "matching", "swap improve"};void process(Driver d[], Passenger p[], int nd, int np) { tic(T_BUILD); buildCandidates(d, p, nd, np); toc(T_BUILD); tic(T_DIST); computeDistances(d, p, nd, np); toc(T_DIST); tic(T_MATCH); greedyMatch(d, p, nd, np); toc(T_MATCH); tic(T_IMPROVE); swapImprove(d, p, nd, np); toc(T_IMPROVE);}// 채점기가 마지막에 부르는 user 함수(또는 process의 마지막 TC)에서:// timerReport(TLAB, 4);
matching 3.1s 78%를 보여주면 — 개선해야 할 곳은 매칭이다. build candidates 0.02s 0.5%인 함수를 아무리 잘 다듬어도 전체는 0.5%밖에 안 줄어든다. 비율이 가장 큰 한 구간이 곧 다음 작업 대상이다. 직감으로 "이 루프가 느릴 것 같다"고 짚었던 곳이 사실 2%였다는 사실을 이 표는 30초 만에 폭로한다.
clock()은 보통 1~15ms 해상도다. 0.1ms짜리 함수를 한 번 재면 0이 나올 수 있다. 해결책은 누적 측정이다 — 위 타이머처럼 같은 id로 수천 번 호출되는 함수의 시간을 합산하면, 개별 호출이 측정 해상도보다 짧아도 누적값은 정확해진다. 또 하나: clock()은 벽시계 시간이 아니라 CPU 시간이다. Sleep()이나 I/O 대기는 잡히지 않지만, 시험 채점기의 연산 코드는 전부 CPU 시간이므로 문제없다. 디버그 빌드(Debug)는 최적화가 꺼져 측정값이 부풀려진다 — 측정은 반드시 Release 빌드로 한다.시간 병목을 찾았으면 다음은 점수 병목이다. 채점기가 출력하는 SCORE는 보통 여러 항목의 합 또는 차다 — "기본 점수 − 이동 비용 − 지연 페널티 + 완료 보너스" 같은 식. 최종 숫자 하나만 보면 어느 항목이 점수를 깎는지 알 수 없다. 그래서 풀이 코드 안에서 같은 항목들을 직접 누적해 분해 출력한다.
// 채점기의 점수 공식을 user 코드에서 그림자처럼 따라 누적한다static long long sb_move = 0; // 이동 비용 총합 (점수를 깎음)static long long sb_delay = 0; // 지연 페널티 총합 (점수를 깎음)static long long sb_done = 0; // 완료 건수 (점수를 올림)static long long sb_unserved = 0; // 미처리 건수 (기회 손실)// 한 배정이 확정될 때마다 호출 — 항목을 누적한다void sbRecord(int moveCost, int delay, int served) { sb_move += moveCost; sb_delay += delay; if (served) sb_done++; else sb_unserved++;}// 한 TC가 끝날 때 호출 — 분해 표를 찍는다void sbReport(int tc) { long long loss = sb_move + sb_delay; printf("--- TC %d 점수 분해 ---\n", tc); printf(" 이동 비용 : %12lld (%.1f%% of loss)\n", sb_move, loss ? sb_move * 100.0 / loss : 0); printf(" 지연 페널티: %12lld (%.1f%% of loss)\n", sb_delay, loss ? sb_delay * 100.0 / loss : 0); printf(" 완료 / 미처리: %lld / %lld\n", sb_done, sb_unserved); fflush(stdout); sb_move = sb_delay = sb_done = sb_unserved = 0; // 다음 TC용 리셋}
이동 비용 92% / 지연 페널티 8%를 보여준다면 — 지연을 줄이는 어떤 정교한 로직도 전체 점수의 8% 안에서만 논다. 진짜 싸움은 이동 비용에 있다. 반대로 미처리 4,200건이 크게 찍히면, 비용을 줄이는 게 아니라 처리율을 올리는 게 급선무다. 점수 분해는 "내 알고리즘이 어디서 점수를 흘리고 있는가"를 한 장의 표로 답한다.
채점기의 정확한 점수 공식을 모를 때도 이 기법은 작동한다. main.cpp의 scoreOfThisTC()(또는 점수 누적 코드)를 §02처럼 정독해 — 어떤 양들이 더해지고 빼지는지 항목 이름만 알아내면 된다. 그 항목들을 user 코드에서 그림자처럼 따라 누적하면 분해가 완성된다. 분해 합이 채점기 SCORE와 거의 일치하면 분해가 정확하다는 검증도 된다.
거의 모든 그리디·휴리스틱 풀이에는 마법의 상수가 한두 개 박혀 있다. 임계값(threshold) TH, 후보 개수 K, 반복 횟수 ITER, 가중치 비율 W — 이런 상수의 값이 점수를 의외로 크게 좌우한다. 그리고 그 최적값은 머리로 계산되지 않는다. 데이터 분포·맵 크기·점수 공식이 얽혀 결정되기 때문이다. 답은 하나뿐이다 — 훑어본다(sweep).
파라미터 스윕은 단순하다. 후보 값들을 for 루프로 돌면서, 각 값으로 풀이를 한 번씩 실행하고 SCORE를 출력한다. 그 출력을 눈으로 훑으면 점수가 어느 값에서 가장 좋은지 보인다. 사람이 상수를 손으로 바꿔가며 컴파일·실행을 반복하는 대신, 코드가 그 반복을 대신 한다.
스윕이 의미를 가지려면 데이터는 고정되고 상수만 변해야 한다. §02에서 봤듯 채점기 시드는 5로 고정돼 있어 make_tc()를 다시 부르면 매번 같은 데이터가 나온다. 따라서 같은 시드 안에서 상수만 바꿔 풀이를 반복하면, 점수 차이는 순수하게 상수의 효과다. 단 하나 주의 — 풀이가 전역 상태(이전 TC의 잔여 배열 등)를 들고 있으면 스윕 반복 사이에 그 상태를 깨끗이 리셋해야 한다. 안 그러면 두 번째 값부터 오염된 상태에서 출발해 점수가 거짓이 된다.
구체적 사례로 본다. 물류배송 문제는 각 배송지를 어느 배송 센터에 묶을지 결정하는 문제다. 한 가지 그리디 전략은 "배송지에서 가까운 센터 중, 이미 부하가 임계값 TH 미만인 센터에 배정"하는 것이다. 이 TH가 마법의 상수다. TH가 크면 가까운 센터에 몰려 일부 센터가 과부하되고, TH가 작으면 부하는 분산되지만 먼 센터까지 배정돼 이동 거리가 늘어난다. 최적값은 그 사이 어딘가에 있다.
이 TH를 스윕했더니 다음과 같은 점수가 나왔다 — 점수는 "총 배송 거리 합"이므로 낮을수록 좋다.
| 임계값 TH | SCORE (총 배송 거리) | 판정 |
|---|---|---|
TH = 50 | 11.36 B (11,360,000,000) | 부하 한계가 헐거워 가까운 센터에 과집중 — 일부 센터 과부하, 그 여파로 거리 폭증 |
TH = 30 | 9.74 B (9,740,000,000) | 분산이 개선되며 1.62 B 하락. 방향이 맞다는 신호 |
TH = 20 | 9.35 B (9,350,000,000) | 추가로 0.39 B 하락. 하락폭이 줄어듦 — 최적값 근처에 접근 |
TH를 50→30→20으로 낮추자 SCORE가 11.36 B → 9.74 B → 9.35 B로 계단식 하락했다. 손으로는 절대 못 찾았을 값이다 — "TH는 클수록 가까운 센터를 쓰니 좋겠지"라는 직감은 정반대였다. 하락폭이 1.62 B에서 0.39 B로 줄어드는 것은 최적값에 다가가고 있다는 신호다. 여기서 TH=15, 10도 더 훑어 하락폭이 0에 수렴하거나 다시 오를 때까지 좁히면 최적값이 잡힌다.
아래는 한 시드 안에서 TH를 자동으로 훑는 완전한 하니스다. 채점기 main.cpp는 건드리지 않고, user 코드 안에 분석 함수 하나를 두는 §01의 "방법 A" 구조를 그대로 쓴다.
// 풀이가 참조하는 전역 튜닝 상수 — 스윕이 이 값을 바꾼다int g_TH = 30; // 본 풀이에서는 이 전역을 임계값으로 읽는다// 한 번의 풀이 실행 → 이 TC의 점수를 돌려준다// (채점기 점수 공식을 user 코드에서 그림자 누적, §2-2 참고)long long runOnce(Center c[], int nc, Order o[], int no) { resetSolverState(); // ← 필수: 이전 실행 잔재 제거 long long dist = 0; for (int i = 0; i < no; i++) { int ci = pickCenter(o[i], c, nc, g_TH); // g_TH를 읽음 dist += manhattan(o[i].pos, c[ci].pos); c[ci].load++; } return dist;}// ── 스윕: TH 후보들을 훑으며 점수를 표로 출력 ──void sweepTH(Center c[], int nc, Order o[], int no) { int cand[] = { 10, 15, 20, 25, 30, 40, 50 }; int nCand = sizeof(cand) / sizeof(cand[0]); long long best = -1; int bestTH = cand[0]; printf("=== TH 스윕 (낮을수록 좋음) ===\n"); for (int k = 0; k < nCand; k++) { g_TH = cand[k]; // 상수만 바꾼다 long long s = runOnce(c, nc, o, no); // 같은 데이터로 재실행 printf(" TH=%3d SCORE=%14lld\n", g_TH, s); if (best < 0 || s < best) { best = s; bestTH = g_TH; } } printf(" → 최적 TH=%d SCORE=%lld\n", bestTH, best); g_TH = bestTH; // 최적값으로 고정하고 끝 fflush(stdout);}
g_TH처럼 전역으로 빼서 풀이 함수가 그것을 읽게 한다 — 그래야 스윕이 한 곳만 바꿔 전체에 반영된다. ② runOnce() 첫 줄의 resetSolverState()는 절대 빠뜨리면 안 된다 — 이게 없으면 두 번째 후보부터 오염된 상태에서 출발한다. ③ 스윕이 끝나면 g_TH를 최적값으로 고정해두고 끝낸다 — 그러면 스윕 함수 호출 한 줄만 주석 처리하면 본 풀이가 최적 상수로 돈다.
한 번의 스윕으로 끝나지 않을 때가 많다. 처음엔 넓고 성기게 훑어 대략의 골짜기를 찾고({10,20,30,40,50}), 그 골짜기 주변을 다시 촘촘히 훑는다({16,18,20,22,24}). 이것을 좁히기 스윕(coarse-to-fine)이라 한다. 물류배송 사례에서 50→30→20으로 하락폭이 줄었다면, 다음은 {12,15,18,20,22}를 훑어 골짜기 바닥을 정밀하게 찾는다.
TH ∈ {10,20,30,40,50}로 5번 실행. SCORE가 20 근처에서 가장 낮게 나오는 것을 확인. 양 끝(10, 50)은 명백히 나쁘므로 골짜기는 그 사이.
TH ∈ {14,16,18,20,22,24}로 6번 실행. 1차에서 찾은 20 주변만 정밀하게 본다. 예컨대 18에서 바닥이면 그 근방으로 한 번 더 좁힐 수도 있다.
TH를 g_TH 초깃값으로 박고, sweepTH() 호출을 주석 처리. 본 풀이는 이제 튜닝된 상수로 돈다. 스윕 코드는 지우지 말고 주석으로 남겨 — 다른 시드에서 재튜닝이 필요할 때 다시 켠다.
for 루프 하나로 얻은 것이다. 시험장에서 알고리즘 대분류가 맞다면(§02 PASS 역산이 "닿는다"고 판정했다면), 스윕은 그 마진을 확보하는 가장 값싼 수단이다.스윕은 한 알고리즘 안에서 상수를 조정한다. 그러나 때로는 알고리즘 자체를 바꿔야 한다 — "가까운 순 그리디" 대신 "정렬 후 매칭"으로, "단순 NN" 대신 "NN + swap 개선"으로. 이때 묻는 질문은 "새 버전이 정말 더 나은가?"이고, 그 답은 같은 데이터에서 두 버전을 직접 겨루는 것으로만 나온다. 이것이 A/B 비교다.
가장 단순한 A/B는 전처리기 스위치다. #if 0 / #if 1로 코드 블록을 켜고 끈다. #if 0 블록은 컴파일러가 통째로 무시하므로, 두 버전을 한 파일에 둬도 한 번에 하나만 컴파일된다.
// ── 이 한 줄만 0/1로 바꿔 버전을 전환한다 ──#define USE_VERSION_B 1 // 0 = 버전 A(기존), 1 = 버전 B(신규)void solve(Order o[], int n) {#if USE_VERSION_B == 0 // ── 버전 A: 입력 순서대로 가까운 센터에 그리디 ── for (int i = 0; i < n; i++) assignNearest(o[i]);#else // ── 버전 B: 외곽 배송지부터 정렬 후 그리디 ── sortByDistanceFromCentroid(o, n); // 먼 것 먼저 for (int i = 0; i < n; i++) assignNearest(o[i]);#endif}
if (useB) { … } else { … }처럼 런타임 분기를 써도 되지만, #if가 더 낫다. ① 꺼진 블록은 컴파일조차 안 되므로 미완성·실험 코드가 들어 있어도 빌드가 깨지지 않는다. ② 런타임 비용이 0 — 분기 예측도, 죽은 코드도 없다. ③ 전환이 딱 한 줄(#define 값)이라 실수 여지가 적다. 시험장에서 "이 줄만 0/1"이라는 단순함은 그 자체로 가치다.
#if 0의 또 다른 용도는 코드 안전 격리다. 개선을 시도하다 망쳤을 때, 잘 되던 버전 A를 지우지 않고 #if 0으로 잠가둔다. 버전 B가 실패하면 #define을 0으로 되돌리는 한 줄로 검증된 버전으로 즉시 복귀한다 — 시험장에는 git이 없으므로, #if가 곧 되돌리기(undo) 장치다.
#if 스위치로 두 버전을 한 번씩 돌려 점수를 비교 — 여기까지는 쉽다. 그러나 치명적 함정이 있다. 채점기 시드는 5 하나로 고정돼 있고, 그 시드 하나에서 B가 A를 이겼다고 해서 B가 진짜 나은 게 아니다. 그 시드 하나의 데이터에서 우연히 B가 잘 맞았을 뿐일 수 있다.
휴리스틱 알고리즘의 점수는 데이터에 따라 출렁인다. A의 평균 점수가 B보다 좋아도, 특정 데이터 한 개에서는 B가 A를 이길 수 있다 — 그건 실력 차가 아니라 분산이다. 시드 하나만 보고 "B가 낫다"고 결론 내리면, 사실은 더 나쁜 알고리즘을 채택하는 사고가 벌어진다. 신뢰할 결론을 얻으려면 여러 시드에서 평균을 비교해야 한다. 채점기 시드는 고정이지만 — 분석용 코드에서는 시드를 우리가 정할 수 있다.
해법은 seed-100 A/B다. 채점기의 데이터 생성 로직(pseudo_rand + make_tc)을 분석 코드 안에서 재현하되, 시드를 1부터 100까지 바꿔가며 매번 새 데이터를 만든다. 그 100개의 데이터 각각에서 A와 B를 모두 돌려 점수를 기록하고, 100개의 평균·승패를 비교한다. 100개 표본의 평균은 한 개 표본보다 훨씬 안정적이라, "B가 진짜 나은가"에 신뢰할 답을 준다.
// 채점기의 LCG를 분석용으로 복제 — 시드를 우리가 정한다static unsigned long long ab_seed;static int ab_rand() { // main.cpp의 pseudo_rand와 동일 식 ab_seed = ab_seed * 25214903917ULL + 11ULL; return (int)((ab_seed >> 16) & 0x3fffffff);}// 채점기 make_tc()를 그대로 옮긴 데이터 생성기// — main.cpp의 생성 코드를 한 줄씩 베껴 온다void genData(unsigned long long seed, Center c[], int& nc, Order o[], int& no) { ab_seed = seed; // ← 시드를 외부에서 주입 nc = ab_rand() % 500 + 501; // 센터 501~1000 no = ab_rand() % 500000 + 500001; // 주문 50만~100만 for (int i = 0; i < nc; i++) { c[i].pos.x = ab_rand() % MAP; c[i].pos.y = ab_rand() % MAP; c[i].load = 0; } for (int i = 0; i < no; i++) { o[i].pos.x = ab_rand() % MAP; o[i].pos.y = ab_rand() % MAP; }}
genData()는 채점기 main.cpp의 make_tc()를 한 줄 한 줄 그대로 옮긴 것이다. % 500 + 501의 숫자, ab_rand() 호출 순서, 루프 범위 — 하나라도 어긋나면 분석이 채점기와 다른 데이터를 보게 되어 결론이 무의미해진다. §02에서 강조했듯 make_tc()를 정독하는 일이 여기서 또 한 번 결정적이다. 시드만 인자로 빼고 나머지는 복사다.
// 버전 A와 B의 풀이 — 점수를 돌려주는 순수 함수로 만든다long long solveA(Center c[], int nc, Order o[], int no);long long solveB(Center c[], int nc, Order o[], int no);static Center cBuf[1024];static Order oBuf[1000001];void seed100AB() { long long sumA = 0, sumB = 0; int winA = 0, winB = 0, tie = 0; printf("=== seed-100 A/B (낮을수록 좋음) ===\n"); for (int s = 1; s <= 100; s++) { int nc, no; // 같은 시드 s로 데이터를 만들어 A와 B에 동일하게 준다 genData(s, cBuf, nc, oBuf, no); long long sa = solveA(cBuf, nc, oBuf, no); genData(s, cBuf, nc, oBuf, no); // B에도 동일 데이터 재생성 long long sb = solveB(cBuf, nc, oBuf, no); sumA += sa; sumB += sb; if (sa < sb) winA++; else if (sb < sa) winB++; else tie++; if (s <= 5 || s % 20 == 0) // 일부만 상세 출력 printf(" seed%3d A=%13lld B=%13lld %s\n", s, sa, sb, sb < sa ? "B win" : "A win"); } printf("--- 종합 (100 시드) ---\n"); printf(" 평균 A = %lld\n", sumA / 100); printf(" 평균 B = %lld\n", sumB / 100); printf(" 승: A %d / B %d / 무 %d\n", winA, winB, tie); double gain = (double)(sumA - sumB) / sumA * 100.0; printf(" B의 평균 개선폭 = %.2f%%\n", gain); fflush(stdout);}
평균 B < 평균 A이고 B win 90 / A win 10이면 — B가 확실히 낫다. 채택한다. 그런데 평균 B < 평균 A인데 B win 55 / A win 45라면 — B의 우위는 얄팍하고, 몇몇 시드에서 큰 차로 이겨 평균을 끌어올렸을 뿐이다. 이때는 "왜 B가 그 45개 시드에서 졌는가"를 들여다봐야 한다. 한 시드만 봤다면 절대 못 봤을 그림이다.
genData(s, …)를 A 실행 전과 B 실행 전에 각각 부른 것에 주목하라. A가 데이터를 변형(센터 load 누적, 주문 정렬 등)했을 수 있으므로, B에게는 깨끗한 데이터를 다시 만들어줘야 한다. 같은 시드 s를 넣으면 ab_rand가 같은 수열을 내므로 데이터는 동일하게 재생된다. 만약 A 실행 후의 오염된 배열을 그대로 B에 넘기면 — B는 A가 망쳐놓은 데이터를 푸는 것이고, 비교는 거짓이 된다. "같은 출발선"이 A/B의 전부다.genData의 주문 수를 강제로 5만 건으로 잘라(no = 50000) 상대 순위만 본다. 알고리즘의 우열은 규모가 작아도 대개 유지된다. seed-100은 이상이고, seed-20·축소데이터는 시험장의 현실적 타협이다.택시 배정 문제의 통과 사례가 A/B 비교의 가치를 보여준다. 기본 풀이(버전 A)는 각 승객을 가장 가까운 택시에 그리디로 붙인다. 그런데 그리디는 순서 의존성이 있어 — 앞에서 좋아 보였던 배정이 뒤에서 손해로 드러난다. 개선안(버전 B)은 그 위에 swap 개선을 얹는다: 두 배정 (택시1↔승객1), (택시2↔승객2)를 골라, 짝을 바꿔 (택시1↔승객2), (택시2↔승객1)로 했을 때 거리 합이 줄면 바꾼다. 이 swap을 500회 반복한다.
// 그리디 매칭 결과를 swap으로 반복 개선한다// match[p] = 승객 p에게 배정된 택시 인덱스void swapImprove(Taxi t[], Passenger p[], int* match, int np) { const int ITER = 500; // ← 스윕 대상 상수(§3) unsigned rs = 98765; // swap용 분석 LCG for (int it = 0; it < ITER; it++) { // 무작위 두 승객 a, b를 고른다 rs = rs * 1103515245u + 12345u; int a = (rs >> 8) % np; rs = rs * 1103515245u + 12345u; int b = (rs >> 8) % np; if (a == b) continue; int ta = match[a], tb = match[b]; // 현재 비용 vs 짝을 바꾼 비용 long long cur = dist(t[ta], p[a]) + dist(t[tb], p[b]); long long alt = dist(t[ta], p[b]) + dist(t[tb], p[a]); if (alt < cur) { // 줄어들 때만 채택 match[a] = tb; match[b] = ta; } }}
ITER = 500은 스윕 대상 상수다 — 100·300·500·1000으로 훑어 점수가 어디서 평평해지는지 본다(보통 일정 횟수 이상은 개선이 미미해진다). 그리고 swap을 얹은 버전 B 전체는 A/B 비교 대상이다 — seed-100으로 "swap이 정말 평균 점수를 올리는가, 몇 %나"를 검증한다. 검증 없이 swap을 넣으면 그건 직감이고, seed-100 A/B를 통과한 swap은 근거다.
B win ≈ 100으로 명확하게 나온다. 남는 질문은 "ITER를 얼마로?"뿐이고, 그건 §3 스윕이 답한다. A/B가 "swap을 쓸 것"을 결정하고, 스윕이 "500회"를 결정한다.
#if 스위치는 그 두 버전을 안전하게 공존시키는 그릇이다.앞의 세 기법은 도구다. 기법 ④는 그 도구들을 하나의 사이클로 엮는 방법론이다. 시험장에서 개선은 한 방의 영감이 아니라 — 작은 사이클을 여러 번 도는 것이다. 그 사이클은 네 박자다: 측정 → 가설 → 수정 → 재측정.
timerReport)와 점수 분해(sbReport)로 "어디가 느린가 / 무엇이 점수를 깎는가"를 한 문장으로 만든다. 이 측정 없이는 사이클을 시작하지 않는다.
#if 스위치(기법 ③)로 버전 B를 만들고, 상수 조정이면 스윕(기법 ②) 대상으로 둔다. 이번 사이클에서는 다른 것을 건드리지 않는다.
#if를 되돌려 수정을 폐기하고, 측정으로 돌아가 다음 후보를 잡는다.
점진 개선 루프의 가장 중요한 규칙이다. 한 사이클에서 두 가지를 동시에 바꾸면 — 점수가 올랐을 때 어느 변경이 효과였는지 알 수 없다. 정렬을 추가하고 임계값도 같이 바꿨는데 점수가 5% 올랐다면, 정렬이 7% 올리고 임계값이 2% 깎았을 수도 있다. 그러면 다음에 정렬은 살리고 임계값은 되돌려야 하는데, 묶어 바꿨으니 그 분리가 불가능하다.
각 사이클은 정확히 하나의 변경만 담는다. 그래야 재측정의 점수 변화가 그 변경 하나에 인과적으로 귀속된다. 변경 A를 넣고 측정, 효과 확인. 그 다음 사이클에서 변경 B를 넣고 측정. 이렇게 하면 어떤 변경이 얼마나 기여했는지 장부에 적히고, 효과 없는 변경은 깔끔히 폐기된다. 두 변경을 묶으면 그 장부가 엉키고, 엉킨 장부는 다음 결정을 모두 추측으로 만든다. — 변경을 묶고 싶은 유혹은 "시간이 없다"는 압박에서 온다. 그러나 묶음이 실패하면 분리에 더 큰 시간이 든다.
점진 개선 루프를 무너뜨리는 또 하나의 적은 조기 최적화(premature optimization)다. 측정하기도 전에 "이 부분이 느릴 게 분명하다"며 정교한 최적화에 시간을 쏟는 것 — 그리고 그 부분이 사실 전체의 2%였다는 것.
코드의 어느 부분이 비용을 먹는지에 대한 인간의 직감은 자주 틀린다. "복잡해 보이는 코드"가 느릴 것 같지만, 실제 병목은 단순해 보이는 루프가 거대한 N에 곱해진 곳인 경우가 많다. 기법 ①의 시간 분해표는 이 직감을 교정한다. 최적화는 측정이 "여기"라고 지목한 곳에만 한다. 측정이 지목하지 않은 곳을 최적화하는 것은 — 잘 돌던 코드를 복잡하게 만들어 버그 위험만 키우고, 점수는 그대로다. "이 코드 우아하지 않은데"라는 미감은 시험장에서 사치다. 측정이 0.5%라고 한 곳은 추하든 말든 내버려 둔다.
네 기법을 종합하면, 시험장의 마지막 30~40분을 쓰는 두 가지 방식이 또렷이 갈린다.
| 국면 | 막무가내 개선 | 체계적 개선 (기법 ①~④) |
|---|---|---|
| 대상 선정 | 코드를 노려보며 "여기가 느릴 것 같다"는 직감으로 고른다 | clock() 시간 분해 + SCORE 점수 분해가 가리키는 한 곳을 고른다 (기법 ①) |
| 상수 값 결정 | "이쯤이면 되겠지" — 한 값으로 박고 넘어간다 | for 루프로 후보를 훑어 SCORE가 최소인 값을 채택 (기법 ②) |
| 개선안 채택 | 한 시드 한 번 돌려 "좋아진 것 같다"는 느낌으로 채택 | seed-100 A/B로 평균·승패를 보고 B win ≥ 90일 때만 채택 (기법 ③) |
| 변경 단위 | 생각나는 것을 한꺼번에 여러 개 바꾼다 | 한 사이클에 한 변경만 — 점수 변화를 그 변경에 귀속 (기법 ④) |
| 되돌리기 | 잘 되던 코드를 덮어써 버려 복구 불가 | #if 0으로 검증된 버전을 잠가두고 한 줄로 복귀 (기법 ③) |
| 실패했을 때 | 무엇이 왜 안 됐는지 모른 채 다음 직감으로 — 시간만 증발 | 재측정이 실패를 즉시 알려줌 → 폐기하고 측정으로 복귀, 손실은 한 사이클 |
| 30분 후 결과 | 점수가 올랐는지조차 불확실, 코드가 망가졌을 수도 | 3~4 사이클 누적 — 각 변경의 효과가 장부에 기록된 검증된 개선 |
네 기법을 다 돌릴 시간이 없을 때의 우선순위. 측정(기법 ①)은 절대 버리지 않는다 — 1~2분이면 끝나고, 그 측정 없이는 나머지가 전부 도박이 된다. 다음으로 지키는 것은 한 번에 한 가지(기법 ④의 핵심 규칙) — 이건 시간이 드는 게 아니라 규율이라 버릴 이유가 없다. 시간에 쫓기면 줄이는 것은 스윕의 후보 개수(7개→3개)와 A/B의 시드 수(100→20)다. 정밀도는 떨어져도 방향은 여전히 맞다. 버리는 것은 정밀도이지 절차가 아니다.
clock()·printf·#if·for 루프만으로 전부 가능하다. 개선은 영감이 아니라 절차다. 그리고 절차는 — 연습할 수 있다.