§ 1문제 정의
은행 출금 시뮬레이션. 1000명의 고객이 각자 다른 금액을 요구하고, 은행은 8종 화폐의 보유량 내에서 정확히 지급해야 한다. 단, 단위가 부족하면 환전 가능 — 다만 5000원 1장 = 1000원 5장 같은 묶음 단위로만.
의도된 정답: 다중제약 배낭 DP. 각 고객 × 각 화폐 조합을 동적 계획으로 풀면 100% 정확. 하지만 1000 × 8 × 최대 잔량 차원의 DP는 메모리·시간 모두 폭주.
실전 베스트는 우선순위 큐 그리디 + 주기적 환전. 매 250 고객마다 “하위 화폐 → 상위 화폐” 환전을 강제로 한 번 돌리면, 잔량 불균형이 누적되지 않는다.
“가장 어려운” 고객이 먼저 처리받아야 한다. 어려움은 그가 요구하는 화폐가 얼마나 부족한지로 정의된다.
§ 2시뮬레이션 — PQ 그리디 + 주기 환전
고객을 “고통 점수” 우선순위 큐에 넣고 하나씩 처리. 250번마다 잔량 환전. 잔량 그래프가 시간에 따라 어떻게 안정화되는지 관찰.
FIG. 17 — coin balance over time
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3왜 250 주기가 최적인가
실험으로 찾은 sweet spot:
| 재조정 주기 k | 정확도 | 특징 |
|---|---|---|
| 10 | 78% | 너무 잦은 환전, 누적 손실 |
| 100 | 83% | 여전히 손실 큼 |
| 200 | 85% | 준수하지만 부족 |
| 250 | 87% | ✓ 최적 — 4회 환전 |
| 500 | 82% | 이미 불균형이 누적됨 |
250이 최적인 수학적 이유:
- 고객 1000명, 화폐 8종 → 화폐당 평균 125명이 영향.
- 환전은 정보 손실: 5000 1장 → 1000 5장으로 가면 “큰 단위 다시 못 만듦.”
- 너무 자주 환전하면 후반 큰 단위 부족, 너무 늦으면 작은 단위 부족.
- √1000 ≈ 31, 1000/4 = 250. 4분할이 분산 최소화 지점.
우선순위 함수의 제곱항(잔량²)이 키. 부족이 클수록 지수적 페널티 → 거의 자동으로 헝가리안 매칭과 비슷한 매핑이 나옴.
§ 4알고리즘 골격
solve():
# 1) 각 고객의 필요 화폐 계산 (그리디 분해)
for c in customers:
c.need[8] = decompose(c.amount)
# 2) PQ 초기 구성 — 고통 점수 우선
pq = PriorityQueue()
for c in customers:
c.prior = computePriority(c, remain)
pq.push(c)
k = 0
while pq not empty:
c = pq.pop()
# 다른 고객 처리로 c.prior이 stale일 수 있음 → 검증
if c.prior < computePriority(c, remain):
c.prior = recompute
pq.push(c)
continue
# 실제 지급
for i in 7..0: # 큰 단위부터
give = min(c.need[i], remain[i])
mResult[c.id][i] = give
remain[i] -= give
c.need[i] -= give
k += 1
# ⭐ 주기적 환전 — 핵심 트릭
if k % 250 == 1:
for i in 7..1: # 하위 → 상위
if remain[i] >= multi[i]:
cvt = remain[i] // multi[i]
remain[i-1] += cvt
remain[i] -= cvt × multi[i]
# 모든 남은 고객 우선순위 재계산
pq.rebuild()
computePriority(c, remain):
p = 0
for i in 0..7:
if remain[i] < c.need[i]:
# 부족 = 제곱 패널티
p += (c.need[i] − remain[i])² × c.need[i]
return p