이 페이지는 "왜 단순 그리디가 Winner를 +4점 넘는가"를 끝까지 따진다. feature별 한계 만족도 α가 어떻게 KKT 최적성 조건을 그리디 정렬로 변환하는지, α의 분리 가능성이 어떻게 greedy choice property를 보장하는지, 그리고 LOOKAHEAD_WEIGHT=0.095라는 좁은 sweet spot이 어떻게 α 추정 분산을 최소화하는지를 수학적으로 해부한다.
TV 화질 문제의 점수는 채점기가 매 턴 누적한다 — Σ Satisfaction − 0.01 × Σ Power. 1,000턴 동안, 20개 화질 feature의 값 val[i] ∈ [0,100]을 정해 만족도 합을 최대화하되, 매 턴 전력 소비가 380을 넘으면 안 된다. 그리고 값을 바꿀 때마다 0.01 × |Δval|의 변경 비용이 붙는다.
이것은 전형적인 제약 하 동적 최적화다. 매 턴 20차원 결정 벡터를 골라야 하고, 비선형 전력 제약이 결정들을 묶으며, 사용자 분포가 시간에 따라 변해 "지금 좋은 feature"와 "곧 좋아질 feature"가 다르다. 베스트 해법은 이 복잡성을 세 겹으로 푼다.
핵심 통찰은 α가 차원을 접는다는 것이다. 20개 feature의 값을 동시에 고민하는 대신, 각 feature를 독립적인 "전력당 효율"로 평가하면 문제는 1차원 정렬이 된다. 그리디가 정당한 이유는 정확히 이 환원이 만든 구조 — §2가 증명한다.
그리디가 "탐욕적"이라는 이름 때문에 최적성을 의심받는 것은 정당한 경계심이다. 그러나 이 문제에서는 두 개의 구조적 사실 — 목적함수의 선형성과 α의 분리 가능성 — 이 그리디를 최적으로 끌어올린다. 먼저 가능성(feasibility)부터 확인한다.
매 턴 그리디 배정 루프가 끝난 시점에 다음이 성립한다: Σi power[i] · val[i]² / 10000 ≤ 380.
루프는 feature를 효율 내림차순으로 순회하며, 각 feature에 값을 줄 때 maxVal = sqrt(10000 · (380 − powerUsed) / power[i])로 상한을 건다 — 이는 남은 예산을 정확히 소진하는 값이다. 따라서 어떤 feature도 누적 전력을 380 위로 밀어 올릴 수 없다. 예산을 넘기면 채점기가 그 턴을 무효 처리하므로, 이 불변식은 점수보다 우선한다.
흔한 오해: "feature가 20개니 전력을 골고루 나눠 모두 50쯤 주면 되지 않나?" — 아니다. 균등 배정의 점수는 약 600,000으로, 베스트의 절반이다. 이유는 명확하다. feature마다 α[i]가 크게 다르다. 사용자 분포의 중앙값에서 먼 median[i]를 가진 feature는 α가 거의 0인데, 균등 배정은 그런 "효과 없는 feature"에도 전력을 똑같이 쏟는다. 380이라는 한정된 예산을 효과 없는 곳에 낭비하면, 정작 효과 큰 feature를 충분히 못 올린다.
목적 Σ val[i]·α[i]가 val에 선형이고, 제약 Σ power[i]·val[i]²/10000 ≤ 380이 val에 볼록일 때, 연속완화(val[i] ∈ [0,100] 실수)의 전역 최적해는 모든 내부 feature가 동일한 한계효율을 갖는 점이다. 이 점은 효율 α[i]/power[i] 내림차순 그리디 배정으로 도달한다.
라그랑지안을 L = Σ α[i]·val[i] − λ(Σ power[i]·val[i]²/10000 − 380)로 둔다. 내부 최적(0 < val[i] < 100)에서 정상조건 ∂L/∂val[i] = 0은 α[i] − λ · power[i]·val[i]/5000 = 0, 즉
val[i]* = 5000 · α[i] / (λ · power[i]).
모든 내부 feature가 같은 라그랑주 승수 λ를 공유하므로, 최적해에서 val[i]는 α[i]/power[i]에 비례한다. λ는 전력 제약을 등호로 만드는 값(예산을 꽉 채우는 그림자가격)으로 유일하게 정해진다.
효율 α[i]/power[i]가 높은 feature가 더 큰 val을 받는다는 것은 — 그리디가 효율 내림차순으로 예산을 채우는 것과 정확히 같은 배분이다. 효율이 낮아 val[i]* ≤ 0이 되는 feature는 경계해 val[i]=0으로 빠지며, 이것이 "효과 없는 feature를 건너뛰는" 그리디의 동작이다.
Theorem 1이 보장하는 것은 연속완화의 최적성이다. 실제 값이 정수라면 그리디는 라운딩 오차만큼 최적에서 벗어난다 — 그러나 그 오차는 feature당 최대 1단위, 전력으로 환산하면 미미하다. 진짜 최적성의 두 번째 기둥은 α의 구조다.
α[i]는 quality[i], median[i], 그리고 사용자 분포 {dist[j]}만의 함수다 — 다른 feature의 값 val[j]에 전혀 의존하지 않는다. 따라서 한 feature를 결정해도 다른 feature의 α가 바뀌지 않는다.
이 분리 가능성이 greedy choice property를 성립시킨다. 그리디 정렬이 "효율 1등 feature에 예산을 먼저 준다"고 할 때, 그 결정이 2등·3등 feature의 효율을 흔들지 않으므로 — 정렬 순서가 배정 도중 무너지지 않는다. 만약 α가 다른 feature 값에 의존했다면(상호작용 효용), 한 결정이 정렬을 재배열해 그리디가 무너졌을 것이다. 효용함수가 feature에 대해 가법적(additive)이라는 점이 그리디를 구한다.
매 턴 solve()는 세 국면을 거친다 — (1) 모든 feature의 α를 현재·미래 분포로 계산하고 가중 혼합, (2) 효율 α/power로 정렬, (3) 전력 예산을 채우며 각 feature의 val을 결정. 아래는 통과 코드의 핵심부다.
const double W = 0.095; // LOOKAHEAD_WEIGHT — sweet spotconst double NOISE = 4.5; // 사용자 이동 노이즈 평균void computeAlpha(double alpha[]) { for (int i = 0; i < NFEAT; ++i) { double aNow = 0, aFut = 0; for (int j = 0; j < NUSER; ++j) { // (1) 현재 분포에서의 한계 만족도 aNow += 1.0 / (fabs(median[i] - userDist[j]) + 1.0); // (2) 2-step lookahead: 사용자가 spot 향해 NOISE 만큼 이동 double proj = userDist[j] + sgn(spotDist[j] - userDist[j]) * NOISE; aFut += 1.0 / (fabs(median[i] - proj) + 1.0); } aNow *= 0.01 * quality[i]; aFut *= 0.01 * quality[i]; // (3) 현재·미래를 W 가중치로 혼합 — 분산 감소 alpha[i] = aNow * (1.0 - W) + aFut * W; }}
sgn(spotDist[j] − userDist[j])는 사용자가 "끌리는 지점(spot)" 쪽으로 이동한다는 모션 모델을 인코딩한다. 노이즈의 평균이 0이 아니라 4.5인 이유다 — 이동은 방향성을 가진다. 미래 분포 proj를 이 방향으로 한 번 밀어 둠으로써, 다음 턴의 α를 미리 추정한다.
void solve(int turn) { double alpha[NFEAT]; computeAlpha(alpha); // 효율 = α / power 내림차순 정렬 int order[NFEAT]; iota(order, order + NFEAT, 0); sort(order, order + NFEAT, [&](int a, int b) { return alpha[a] / power[a] > alpha[b] / power[b]; }); double powerUsed = 0; for (int k = 0; k < NFEAT; ++k) { int i = order[k]; double remain = 380.0 - powerUsed; if (remain <= 0) { val[i] = 0; continue; } // 남은 예산이 허용하는 최대 val: power·v²/10000 ≤ remain double maxV = sqrt(10000.0 * remain / power[i]); double cap = min(100.0, maxV); // KKT 비례식 val ∝ α/power, 변경비용 0.01·|Δval| 반영 int v = chooseVal(alpha[i], power[i], cap, prevVal[i]); val[i] = v; powerUsed += power[i] * (double)v * v / 10000.0; } memcpy(prevVal, val, sizeof(val)); // 다음 턴 변경비용 기준}
chooseVal이 prevVal[i]를 인자로 받는 이유는 변경 비용 0.01·|Δval| 때문이다. KKT 비례식이 제안하는 이상값과 직전 값이 가깝다면, 굳이 바꿔 변경 비용을 물 이유가 없다 — 작은 개선이 변경 비용보다 작으면 값을 유지하는 것이 점수에 유리하다. 이 히스테리시스가 1,000턴 누적 변경 비용을 억제한다.
턴당 비용은 computeAlpha의 O(NFEAT · NUSER) = O(20 · 800) = 1.6×10⁴가 지배한다. 정렬은 O(NFEAT log NFEAT) ≈ 20·4.3 ≈ 86, 배정 루프는 O(NFEAT)=20으로 무시할 수준이다. 1,000턴 전체는 ~1.6×10⁷ 연산 — -O2에서 즉시 끝난다. lookahead가 α 계산을 2배로 만들지만(현재+미래), 상수배일 뿐 차수는 그대로다.
1-step α-greedy는 약 1,210,000점, 2-step lookahead를 더하면 1,224,956점 — Winner를 +4점 넘는다. 그 +14,956점의 대부분과 결정적 +4점은 단 하나의 상수, W = LOOKAHEAD_WEIGHT = 0.095에서 나온다. 왜 하필 0.095인가?
현재 분포로만 계산한 αnow는 이번 턴에 대해서는 정확하지만, val은 이번 턴 동안 유지되며 사용자는 그 사이 이동한다. 따라서 진짜 최적화 대상은 "이번 턴 + 다음 턴"에 걸친 α의 평균이다. 미래 분포로 계산한 αfuture는 그 평균에 더 가깝지만 — 모션 모델이 노이즈를 포함하므로 추정 자체에 분산이 있다.
α 추정의 평균제곱오차 MSE(W) = Bias(W)² + Var(W)는 W에 대해 볼록이며, 유일한 최소점 W*를 갖는다. W*는 미래 분포의 불확실성 σ²fut이 클수록 작아진다 — 노이즈가 심한 추정에는 가중치를 적게 줘야 한다.
Bias(W) = (1−W)·Δ(Δ는 미래를 무시할 때의 고정 편향), Var(W) ≈ (1−W)²σ²now + W²σ²fut로 근사한다. 그러면
MSE(W) = (1−W)²Δ² + (1−W)²σ²now + W²σ²fut.
dMSE/dW = −2(1−W)(Δ²+σ²now) + 2W·σ²fut = 0을 풀면
W* = (Δ²+σ²now) / (Δ²+σ²now+σ²fut).
2차 도함수가 양수이므로 이 점은 최소다. σ²fut가 커질수록 분모가 커져 W*가 작아진다. 사용자 이동 노이즈(평균 4.5)가 미래 분포를 크게 흔들기 때문에 σ²fut가 지배적이고, 그 결과 W*가 0.095라는 작은 값으로 떨어진다.
이론은 "W가 작다"까지만 말한다. 정확히 0.095라는 값은 Δ, σnow, σfut를 닫힌 형태로 알 수 없으므로 — 실험으로 sweep해 찾는다. 문제 페이지가 명시하듯 0.10도 0.09도 점수가 떨어진다. MSE 곡선이 W* 근처에서 볼록하므로 최소점은 좁고 뾰족하며, 그 0.005 폭 안에서의 미세 조정이 Winner를 넘는 마지막 +4점의 정체다.
W를 0.3, 0.5로 키우면 점수가 급락한다. 직관과 어긋난다 — "미래를 더 보는 게 낫지 않나?" 그러나 미래 분포는 추정이고, 추정의 노이즈를 α에 그대로 흘려보내면 효율 정렬 순서가 뒤집힌다. 잘못 뒤집힌 순서는 효과 없는 feature에 예산을 주는 균등 배정의 실수를 재현한다. lookahead는 편향을 줄이되 분산을 사들이는 거래이며, 거래가 남는 구간은 W ≈ 0.095 부근의 좁은 띠뿐이다.
| 전략 | 점수 | 제약 처리 | 한계 |
|---|---|---|---|
| 균등 배정 (모든 val=50) | ~600,000 | 고정 | 효과 없는 feature에 전력 낭비 |
| val 최대화 그리디 (α 무시) | ~950,000 | 초과 빈번 | 전력 380 제약을 못 지킴 |
| Simulated Annealing | ~1,180,000 | 탐색 | 턴당 탐색 예산 부족 |
| α-greedy (1-step) | ~1,210,000 | KKT | 사용자 이동을 내다보지 못함 |
| α-greedy + 2-step lookahead | 1,224,956 | KKT | Winner(1,224,952) 초과 — sweet spot 의존 |
표는 두 개의 분리된 경쟁을 보여준다. 첫째는 제약 처리 — val 최대화 그리디는 점수가 높아 보이지만 전력 380을 못 지켜 무효다. α-greedy 계열만이 KKT 구조로 제약을 정확히 만족시킨다. 둘째는 α 추정 품질 — SA는 탐색으로 풀려다 시간이 부족하고, 1-step은 사용자 이동을 무시해 미래 턴에서 손해를 본다. 2-step lookahead가 편향-분산 최적점(Theorem 3)에서 α를 추정함으로써 마지막 격차를 메운다.
결론의 구조는 §1의 분해와 같다. α가 차원을 접어 그리디를 가능케 하고(Theorem 1·Lemma), lookahead가 동적 분포 변화를 분산 최소로 흡수한다(Theorem 3). 두 정리가 합쳐져 단순 그리디가 무작위 탐색(SA)을 이긴다.
val[j]가 끼어들면 Lemma의 분리 가능성이 깨져, 한 결정이 정렬 순서를 흔든다. computeAlpha는 quality·median·사용자 분포만 봐야 한다. feature 간 상호작용을 모델링하고 싶다면 그리디 자체를 포기해야 한다.
power[i]·val[i]²/10000로 val의 제곱에 비례한다. 선형으로 착각해 maxVal을 remain/power로 계산하면 예산을 초과한다. 상한은 반드시 sqrt(10000·remain/power[i])여야 한다.
0.01·|Δval| 변경 비용이 1,000턴 누적된다. chooseVal이 prevVal과 비교해, 개선폭이 변경 비용보다 클 때만 값을 바꾸는 히스테리시스를 둬야 한다.
W를 0.3~0.5로 키우면 미래 분포 추정의 노이즈가 α로 새어 들어가 정렬이 뒤집힌다(Theorem 3). W는 0.09~0.10의 좁은 띠 안에 있어야 하며, sweep으로 0.095를 확인하라.
spotDist 방향으로 NOISE만큼 민다. sgn(spotDist−userDist) 부호를 반대로 두면 사용자가 끌리는 지점에서 멀어지는 것으로 모델링되어 αfuture가 완전히 틀어진다.
이 풀이가 "Winner를 넘었다"는 주장의 근거는 채점기 출력이다. 채점기는 매 턴 전력 제약 위반을 검사(위반 시 그 턴 무효)하고, Σ Satisfaction − 0.01·Σ Power를 1,000턴 누적한다.
main.cpp는 고정 seed로 800 user·20 feature·1000 turn 시나리오를 생성하고, 매 턴 solve()가 반환한 val[]로 전력·만족도를 계산한다. g++ -O2로 main.cpp + user.cpp를 함께 컴파일하면 누적 SCORE: 1224956이 출력되며, Winner 기록 1,224,952를 +4점 상회한다. LOOKAHEAD_WEIGHT를 0.09 또는 0.10으로 바꿔 재실행하면 점수 하락이 직접 관찰되어, sweet spot의 존재를 실험적으로 확인할 수 있다.