알고리즘 · LESSON 5
Floyd 샘플링 - 중복당첨 막기
대량 응모자 추첨여러 명을 뽑을 때 같은 사람이 또 나오면 안 돼요. Floyd는 '다시 뽑기' 없이 중복을 깔끔히 없애는 똑똑한 방법이에요.
핵심
Floyd의 한 줄 비밀
후보를 한 명씩 늘려가며 뽑아요. 그런데 뽑은 번호가 이미 당첨자면? 다시 뽑지 말고 '방금 새로 들어온 후보'에게 그 자리를 줘요.
왜 통할까? 방금 들어온 후보는 아직 한 번도 안 뽑힌 번호라, 넣어도 절대 또 겹치지 않아요. 그래서 다시 뽑을 필요가 없어 빨라요.
비교
그냥 '다시 뽑기'는 왜 힘들까?
가장 쉬운 방법은 "뽑았는데 이미 당첨자면 버리고 다시 뽑기"예요. 그런데 난수라서 운이 나쁘면 같은 사람이 자꾸 나올 수 있어요. 그러면 몇 번을 다시 뽑아야 할지 아무도 몰라요(예측 불가).
특히 거의 다 뽑아서 남은 자리가 얼마 없을 때, 이미 당첨된 사람만 계속 나와서 헛탕(다시 뽑기)을 엄청 반복할 수 있어요.
6명 중 5명을
버튼을 여러 번 눌러봐요. 걸린 횟수가 매번 들쭉날쭉하죠? 운 나쁘면 훨씬 많아요. 반면 Floyd는 언제나 딱 5번(헛탕 0번)이라 빠르고 예측도 돼요.
개념
5명인데 왜 '3명'부터 시작할까?
뽑을 사람이 3명이니 추첨도 3번만 하면 돼요. 그리고 마지막 회차엔 5명 모두가 후보여야 공평하죠. 마지막(3번째) 회차엔 후보가 5명, 한 회차 앞으로 갈 때마다 후보가 1명씩 줄어요: 5명 → 4명 → 3명. 그래서 첫 회차는 후보 3명으로 시작해요.
그래서 5 − 3 + 1 = 3, 즉 3명부터 시작해요. 빨강 = 그 회차에 새로 들어온 후보
실험
한 회차씩 따라가기 (5명 중 3명)
'뽑기' 버튼을 누르면 한 회차씩 진행돼요. 회차마다 후보가 1명씩 늘어요.
검증
왜 공정할까? — 직접 확인하기
먼저 들어온 번호는 여러 번 뽑힐 기회가 많고, 늦게 들어온 번호는 중복이 생기면 대신 뽑혀요. 이 둘이 정확히 상쇄돼서 모두 똑같은 확률(뽑는 수 ÷ 사람 수)이 돼요.
8명 중 3명을 5,000번 뽑아 각 응모자의 당첨 횟수를 비교해봐요.
menu_book참고문헌 · Floyd 샘플링
- Bentley, J. L., & Floyd, B. (1987). Programming Pearls: A Sample of Brilliance. Communications of the ACM, 30(9), 754–757.
- Robert Floyd's Tiny and Beautiful Algorithm. nowherenearithaca.com
- A Sample of Brilliance. Fermat's Library. fermatslibrary.com/s/a-sample-of-brilliance