알고리즘 · LESSON 6 · 방식 ②
가중치 키 추첨 — Efraimidis–Spirakis
응모자마다 난수로 'Key 값'을 계산해요. 가중치가 클수록 작은 Key가 나오기 쉽고, Key값이 작은 순서대로 당첨돼요. 정렬 한 번으로 여러 명을 중복 없이 뽑아요.
개념
Key = −ln(u) / w
응모자마다 0~1 사이 난수 u를 하나 뽑고, 가중치 w로 Key = −ln(u) / w를 계산해요. 여기서 ln은 자연로그예요. 가중치 w가 클수록 Key가 작아지죠. 모든 응모자를 Key가 작은 순서대로 정렬하면, 앞에서부터가 곧 당첨 우선순위예요.
key = −ln(u) / wu : 0~1 사이 난수 · w : 응모자의 가중치. 가중치가 클수록 Key가 작아져 더 앞 순위가 돼요.
왜 통할까? −ln(u)는 난수를 가중치 적용에 알맞은 값으로 바꿔줘요. 그 결과 당첨 확률이 가중치에 비례하면서도, 충돌·재추첨 없이 정렬 한 번으로 끝나요.
실험
예시 따라가기 — 4명 중 2명
가중치가 다른 4명의 난수 u와 Key 에요. Key값이 작은 2명이 당첨돼요.
| 응모자정보 | 가중치 w | 난수 u | Key = −ln(u)/w | 순위 |
|---|
검증
진짜 가중치대로일까? — 5,000번 뽑기
가중치 1·2·3·4점을 가진 4명 중 2명을 여러 번 뽑아 당첨 횟수를 비교해봐요. 가중치가 클수록 더 자주 당첨될까요?
가중치가 클수록 작은 Key가 나올 확률이 커서 더 자주 당첨돼요. 하지만 난수는 무작위라, 가중치가 낮은 사람도 당첨될 때가 있죠 — 그래서 공정한 '추첨'이에요.
menu_book참고문헌 · 가중치 키 추첨
- Efraimidis, P. S., & Spirakis, P. G. (2006). Weighted Random Sampling with a Reservoir. Information Processing Letters, 97(5), 181–185.