알고리즘 · LESSON 4
불공정 난수 버리기
가중치 구간 추첨대량 응모자 추첨주사위(1~6)로 친구 5명을 공평히 뽑으려면? 5로 안 나눠떨어지는 6은 불공정한 난수예요. 그럴 땐 버리고 다시 굴려요.
개념
주사위 1~6으로 5명을 뽑으면?
주사위 값으로 5로 나눈 나머지로 당첨 번호를 정해봐요. (이 예시는 나머지에 +1을 더하지 않고, 나머지 값 그대로 당첨 번호가 되고 나머지가 0일 때는 5번이 당첨번호가 되는 걸로 가정했어요.)
| 주사위 | ÷ 5 | 나머지 | → 당첨 |
|---|---|---|---|
| 1 | 몫 0 | 1 | 1번 |
| 2 | 몫 0 | 2 | 2번 |
| 3 | 몫 0 | 3 | 3번 |
| 4 | 몫 0 | 4 | 4번 |
| 5 | 몫 1 | 0 | 5번 |
| 6 | 몫 1 | 1 | 1번 (또!) |
주사위는 6까지 있는데 사람은 5명. 그래서 6은 1번을 또 가리켜요 → 1번만 두 배 유리해져 불공정해요. 그래서 6은 거부하고 다시 굴려요. (나머지 0은 마지막 5번)
실험
실제 추첨 시뮬레이션 — 직접 굴려보기
'공정'은 6을 거부하고 다시 굴려요. '불공정'은 6도 그대로 써요. 많이 굴려 막대 높이를 비교해봐요.
16이 나왔을 때 어떻게 할지 골라요
2주사위를 여러 번 굴려서 결과를 확인해 보세요
공정 모드는 불공정한 난수(6)를 거부하고 다시 굴려서 막대가 평평해요. 불공정 모드는 6도 1번에게 줘서 1번만 높아져요.
menu_book참고문헌 · 거부법(불공정 난수 버리기)
- von Neumann, J. (1951). Various Techniques Used in Connection with Random Digits. National Bureau of Standards, Applied Mathematics Series, 12, 36–38.
- Lemire, D. (2019). Fast Random Integer Generation in an Interval. ACM Transactions on Modeling and Computer Simulation, 29(1), Article 3.