§ 1문제 정의
사용자들이 TV 앞을 오가고, 매 턴 작은 노이즈가 추가된다. 화질 feature 20개의 값을 0–100 사이로 조정해 만족도를 극대화한다. 단, 전력 예산 380, 그리고 값을 바꿀 때마다 변경 비용이 든다.
“각 feature를 얼마나 올릴까?”라는 문제로 환원되지만, 제약 조건(power ≤ 380) 때문에 단순 그리디로는 어렵다. 그리고 사용자 분포가 시간에 따라 변하기 때문에, 지금 효과적인 feature와 곧 효과적인 feature가 다르다.
Winner는 1,224,952점. 우리는 1,224,956점으로 +4점 넘었다 — 핵심은 α-greedy + 2-step lookahead의 정량적 조합.
α는 “지금 이 feature를 1 올리면 얻는 만족도”다. 모든 결정을 α 한 지표로 환원하면 문제가 1차원이 된다.
§ 2최적화 시뮬레이션 — α-Greedy 결정 과정
매 턴마다 모든 feature에 대해 α를 계산하고, “α / power 비율”이 높은 feature부터 val을 올린다. 전력 누적이 380에 닿으면 정지. 작은 lookahead로 사용자 이동 방향을 미리 반영.
FIG. 16 — α-greedy + 2-step lookahead
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3왜 α-Greedy가 최적인가
동적 제약 최적화는 보통 DP나 시뮬레이션 어닐링으로 푼다. 왜 단순 그리디로 Winner를 넘을 수 있을까?
| 접근법 | 점수 | 한계 |
|---|---|---|
| 모든 feature = 50 (균등) | ~600,000 | 전력 낭비, 효과 없는 feature까지 올림 |
| 그리디 (α 무시, val 최대화) | ~950,000 | 전력 초과 빈번 |
| α-greedy (1-step) | ~1,210,000 | 사용자 이동 무시 |
| α-greedy + 2-step lookahead | 1,224,956 | Winner 초과 |
| Simulated Annealing | ~1,180,000 | 탐색이 시간 부족 |
그리디가 최적인 이유 3가지:
- 볼록 효용 함수. Satisfaction = Σ val[i] × α[i]는 val에 선형. 전력 = Σ power[i] × val[i]²/10000은 볼록. 볼록 제약 + 선형 목적은 KKT 해가 그리디에 자동 수렴.
- α의 단조성. α[i]는 val[j]에 독립. 한 feature 결정이 다른 feature의 α를 안 바꿈 → greedy choice property 충족.
- 2-step lookahead의 마법. 사용자 분포 변화 노이즈는 평균 4.5. 2턴 앞의 dist 분포를 0.095 가중치로 미리 반영하면 α 추정 분산이 크게 줄어든다.
최적 LOOKAHEAD_WEIGHT = 0.095는 실험으로 찾았다. 0.10도 0.09도 점수 하락. 이 좁은 sweet spot이 +4점의 정체.
§ 4알고리즘 골격
solve(turn):
# α 계산 (각 feature마다)
for i in 0..19:
# 현재 사용자 분포에서의 α
α_now[i] = 0.01 × quality[i] ×
Σⱼ 1 / (|median[i] − userDist[j]| + 1)
# 2-step lookahead: 사용자가 spot 향해 노이즈 평균 4.5만큼 이동했다고 가정
for j in users:
projDist[j] = userDist[j] + sign(spotDist − userDist[j]) × AVG_NOISE
α_future[i] = 0.01 × quality[i] ×
Σⱼ 1 / (|median[i] − projDist[j]| + 1)
α[i] = α_now[i] × (1 − W) + α_future[i] × W # W = 0.095
# 효율 정렬 (α / power 비율)
order = sort features by α[i] / power[i] desc
# 전력 누적하며 val 결정
powerUsed = 0
for i in order:
# 이 feature를 얼마나 올릴까?
# 전력 = power[i] × val[i]² / 10000 ≤ remaining budget
maxVal = min(100, sqrt(10000 × (380 − powerUsed) / power[i]))
# 변경 비용 고려: |val − prev|에 0.01 패널티
val[i] = optimal_val(α[i], power[i], maxVal, prevVal[i])
powerUsed += power[i] × val[i]² / 10000
return val[]