가중치 구간 추첨

알고리즘 · LESSON 6 · 방식 ①

응모자마다 가중치 크기만큼 '당첨 구간'을 줘요. 1부터 가중치 총합까지 중 난수 하나를 뽑아, 그 수가 떨어진 구간의 주인을 당첨시켜요.

개념

응모자를 한 줄로 세우고, 각자 가중치만큼 자리(구간)를 차지하게 해요. 가중치가 클수록 구간이 넓어지죠. 그다음 1 ~ 가중치 총합 사이에서 난수('당첨 기준값')를 하나 뽑아, 그 수가 들어간 구간의 응모자를 당첨자로 골라요.

왜 공정할까? 구간이 넓을수록(=가중치가 클수록) 난수가 그 안에 떨어질 확률이 커요. 그래서 당첨 확률이 정확히 가중치에 비례해요.

실험

가중치가 다른 4명(A·B·C·D)의 당첨 구간이에요. '당첨 기준값 뽑기'를 누르면 1~10 사이 난수가 떨어진 구간의 주인이 당첨돼요.

응모자 정보

응모자별 가중치 구간

110

난수가 넓은 구간(가중치 높은 사람)에 떨어질 확률이 더 커요. 그래서 가중치가 클수록 더 자주 당첨돼요.

검증

가중치 1·2·3·4점을 가진 4명을 여러 번 뽑아 당첨 횟수를 세어 봐요. 막대 높이가 가중치 비율(1:2:3:4)과 비슷해지면 공정한 거예요.

menu_book참고문헌 · 가중치 구간 추첨

Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3rd ed.), §3.4.1. Addison-Wesley.