가중 무작위 추출(별칭 방법) 계산기

확률이 서로 다른 항목 중 하나를 O(1)에 뽑게 해 주는 표를 만드는 방법입니다. 1974년 워커(Walker)가 낸 것으로, 칸 n개짜리 상자에 각 항목의 확률×n만큼 물을 붓고 넘치는 칸에서 모자란 칸으로 물을 옮겨 모든 칸 높이를 1로 맞춥니다. 채워진 칸에는 원래 주인과 물을 대 준 항목이 「별칭」으로 함께 남습니다.

뽑기 한 번의 비용이 O(log n)에서 O(1)로 줄어듭니다. 누적합 방식은 난수 하나를 누적 배열에서 이분 탐색해야 하지만, 별칭 방법은 주사위를 굴려 칸을 고르고 동전을 한 번 던져 그 칸의 두 후보 중 하나를 고르면 끝입니다. 대신 표를 만드는 데 O(n)이 들고, 확률이 바뀌면 표를 다시 만들어야 합니다.

난수 u에 항목 수 n을 곱해 정수부로 칸을, 소수부로 동전을 대신합니다. u = 0.42이고 n = 3이면 1.26이 되어 1번 칸(0부터 세어)을 고르고 0.26을 그 칸의 주인 몫과 견줍니다. 난수 발생기를 한 번만 부르면 되니 실제 구현에서 흔히 쓰는 방법입니다.

표를 훑어 각 항목이 뽑힐 확률을 정확히 합산해 입력 확률과 비교합니다. 항목 k의 확률은 (1/n)×[칸 k의 주인 몫 + 별칭이 k인 칸들의 남은 몫의 합]입니다. 이 계산기는 이 값을 분수로 통분해 입력과 같은지 보므로 「거의 같다」가 아니라 정확히 같은지를 확인합니다.

부동소수점 누적 오차가 표를 망가뜨리기 때문입니다. 물을 옮길 때마다 뺄셈이 쌓이면 마지막 칸이 1에서 미세하게 어긋나고, 큰 쪽·작은 쪽 판정이 뒤집혀 남은 항목이 잘못된 별칭을 갖게 됩니다. 이 계산기는 가중치를 정수로 스케일해 정수 비교만으로 표를 만듭니다.

쓸 수 있습니다. 「SSR:0.6, SR:5.4, R:94」처럼 퍼센트를 그대로 넣으면 되고, 합이 100이 아니어도 알아서 비율로 다룹니다. 다만 이 계산기가 보이는 것은 표와 이론 확률이지, 실제 게임의 천장·픽업 같은 규칙은 다루지 않습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.