유니피커 추첨로직
유니피커의 주요 추첨 로직을 확인할 수 있어요.
유니피커는 아래와 같은 로직으로 당첨자를 선정한다.
- ‘시드 발급 서버’에서 ‘시드’를 발급받는다.‘시드’를 ‘난수 생성 알고리즘’에 입력값으로 전달한다.
- 응모자마다 난수를 할당한다.
- 난수를 기준으로 응모자를 정렬한다.
- 그룹 추첨 유형은 추첨 설정 정보에도 난수를 할당한다.그룹 추첨이란 그룹별로 당첨자를 뽑는 추첨을 말한다. 이러한 유형의 추첨에는 그룹정보(등수나 경품명, 아파트 동/호수 같은 당첨자를 구분하는 정보)별로 당첨자 수를 정하는 추첨 설정 정보를 입력해야 한다. 유니피커는 응모자뿐만 아니라 추첨 설정 정보에도 난수를 할당한다.
- 난수를 기준으로 추첨설정 정보를 정렬한다.
- 정렬한 응모자를 순서대로 뽑아 정렬한 추첨 설정 정보에 할당(당첨)한다.
| 응모자정보 | 난수 |
|---|---|
| 홍길동 | 0.377773 |
| 강호동 | 0.786715 |
| 유재석 | 0.683418 |
| 김성주 | 0.492963 |
| 전현무 | 0.921976 |
| 지석진 | 0.478865 |
| 김용만 | 0.231243 |
| 추첨 설정 정보 | 난수 |
|---|---|
| 101동 101호 | 0.878389 |
| 101동 504호 | 0.143862 |
| 103동 502호 | 0.452717 |
| 105동 701호 | 0.451116 |
| 105동 903호 | 0.260410 |
| 응모자정보 | 난수 |
|---|---|
| 전현무 | 0.921976 |
| 강호동 | 0.786715 |
| 유재석 | 0.683418 |
| 김성주 | 0.492963 |
| 지석진 | 0.478865 |
| 홍길동 | 0.377773 |
| 김용만 | 0.231243 |
| 추첨 설정 정보 | 난수 |
|---|---|
| 101동 101호 | 0.878389 |
| 103동 502호 | 0.452717 |
| 105동 701호 | 0.451116 |
| 105동 903호 | 0.260410 |
| 101동 504호 | 0.143862 |
| — | — |
| — | — |
유니피커 가중치 추첨 방식은 가중치 구간 추첨 방식과 가중치 키 추첨 방식 2가지가 있다.
가중치 당첨자 추첨 로직에서 사용되는 난수는 시드 생성 과정을 제외하고, SHA-256(시드|N) 방식¹ 또는 xoshiro(시드) 방식² 중 하나를 선택하여 이용할 수 있다.
유니피커는 가중치 당첨자 추첨 로직 중 가중치 구간 추첨을 다음과 같은 방식으로 적용한다.
- 응모자 리스트를 무작위로 섞는다.응모자 리스트를 피셔-예이츠(Fisher-Yates) 셔플 알고리즘³을 이용하여 무작위로 섞는다. 셔플된 순서에 따라 응모자가 배치되고, 각 응모자는 가중치에 비례하는 크기의 당첨 구간을 갖는다.
- 추첨 설정 정보를 무작위로 섞는다.추첨 설정 정보를 피셔-예이츠 셔플 알고리즘³을 이용하여 무작위로 섞는다.
- ‘당첨 기준값’을 생성한다.(1) ‘당첨 기준값’의 범위는 1부터 ‘응모자 가중치 총합’까지이다. (2) 해당 범위 내에서 난수를 생성하여 ‘당첨 기준값’으로 사용한다. 예) ‘응모자 가중치 총합’이 600일 때, 난수 생성 범위는 1부터 600까지이다.
- 당첨자를 선정한다.응모자 리스트를 순서대로 순회하여 ‘당첨 기준값’이 특정 응모자의 ‘당첨 구간’에 포함되는 경우 해당 응모자를 당첨자로 선정한다.
- 당첨자를 추첨 설정 정보에 할당한다.선정된 당첨자를 셔플된 추첨 설정 정보에 순서대로 할당한다. 모든 추첨 설정 정보에 당첨자가 할당될 때까지 3부터 6까지의 과정을 반복한다.
- 당첨자로 선정된 응모자는 이후 추첨 대상에서 제외한다.남은 응모자를 기준으로 당첨 구간을 다시 설정하고, 응모자 가중치 총합을 재계산한다. 예) 가중치 총합이 600이고 당첨자의 가중치가 160일 때, 다음 범위는 1부터 440까지이다.
| 응모자정보 | 가중치 (W) |
|---|---|
| 김철수 | 150 |
| 나유미 | 50 |
| 지석진 | 10 |
| 이영희 | 200 |
| 김용만 | 160 |
| 안성준 | 100 |
| 전현무 | 30 |
셔플
| 응모자정보 | 가중치 (W) |
|---|---|
| 안성준 | 100 |
| 이영희 | 200 |
| 김철수 | 150 |
| 나유미 | 50 |
| 전현무 | 30 |
| 지석진 | 10 |
| 김용만 | 160 |
맨 끝(7번째) 자리 응모자를 1~7 중 무작위 추첨된 5번째 자리의 응모자와 자리 교환 (전현무 ↔ 김용만)
그 앞(6번째) 자리 응모자를 1~6 중 무작위 추첨된 3번째 자리의 응모자와 자리 교환 (안성준 ↔ 지석진)
…
| 추첨 설정 정보 |
|---|
| 1등 |
| 2등 |
| 3등 |
셔플
| 추첨 설정 정보 |
|---|
| 2등 |
| 1등 |
| 3등 |
맨 뒤(3번째)의 설정 정보를 1~3 중 무작위 추첨된 3번째 자리의 설정 정보와 자리 교환(자리가 동일하므로 교환 없음)
그 앞(2번째)의 설정 정보를 1~2 중 무작위 추첨된 1번째 자리의 설정 정보와 자리 교환
난수 생성
| 응모자정보 | 가중치 | 당첨 구간 | |
|---|---|---|---|
| 안성준 | 100 | 1 ~ 100 | |
| 이영희 | 200 | 101 ~ 300 | |
| 당첨자 선정 | 김철수 | 150 | 301 ~ 450 ← 412 당첨기준값 |
| 나유미 | 50 | 451 ~ 500 | |
| ⋮ | ⋮ | ⋮ | |
| 김용만 | 160 | 541 ~ 700 |
김철수 제외 후 가중치 총합 700 → 550으로 변경, 남은 응모자의 당첨 구간이 재계산된다.
- [1] Durstenfeld, R. (1964). Algorithm 235: Random Permutation. Communications of the ACM, 7(7), 420.
- [2] Fisher–Yates Shuffle. Wikipedia. en.wikipedia.org/wiki/Fisher-Yates_shuffle
유니피커는 가중치 당첨자 추첨 로직 중 가중치 키 추첨을 다음과 같은 방식으로 적용한다.
- 응모자마다 난수를 할당한다.응모자 전원에게 각각 0~1 사이의 난수(u)를 하나씩 발급한다.
- 응모자별 가중치를 반영한 Key값을 생성한다.발급된 난수(u)와 응모자의 가중치(w)를 이용하여 각 응모자의 키 값을 계산한다. 가중치가 클수록 더 작은 Key 값이 생성될 가능성이 높으며, Key 값이 작은 순서대로 당첨 우선순위가 결정된다.
- 응모자 리스트를 계산된 Key 값을 기준으로 오름차순 정렬한다.
- 추첨 설정 정보를 무작위로 섞는다.추첨 설정 정보를 피셔-예이츠 셔플 알고리즘¹을 이용하여 무작위로 섞는다.
- Key 값 순으로 정렬된 응모자를 순서대로 셔플된 추첨 설정 정보에 할당(당첨)한다.
※ Efraimidis–Spirakis(2006)가 제안한 가중 표본추출 알고리즘을 기반으로 한다.
| 응모자정보 | 가중치 (W) | 난수 (U) | −ln(u) | key=−ln(u)/w |
|---|---|---|---|---|
| 김철수 | 150 | 0.73 | 0.3147 | 0.002098 |
| 나유미 | 50 | 0.41 | 0.8916 | 0.017832 |
| 지석진 | 10 | 0.95 | 0.0513 | 0.005129 |
| 이영희 | 200 | 0.12 | 2.1203 | 0.010601 |
| 김용만 | 160 | 0.53 | 0.6349 | 0.003968 |
| 안성준 | 100 | 0.75 | 0.2877 | 0.002877 |
| 전현무 | 30 | 0.44 | 0.8210 | 0.027366 |
| 정렬 순위 | 응모자정보 | 가중치 (W) | 난수 (U) | −ln(u) | key=−ln(u)/w |
|---|---|---|---|---|---|
| 1 | 김철수 | 150 | 0.73 | 0.3147 | 0.002098 |
| 2 | 안성준 | 100 | 0.75 | 0.2877 | 0.002877 |
| 3 | 김용만 | 160 | 0.53 | 0.6349 | 0.003968 |
| 4 | 지석진 | 10 | 0.95 | 0.0513 | 0.005129 |
| 5 | 이영희 | 200 | 0.12 | 2.1203 | 0.010601 |
| 6 | 나유미 | 50 | 0.41 | 0.8916 | 0.017832 |
| 7 | 전현무 | 30 | 0.44 | 0.8210 | 0.027366 |
| 추첨 설정 정보 |
|---|
| 1등 |
| 2등 |
| 3등 |
셔플
| 추첨 설정 정보 |
|---|
| 2등 |
| 1등 |
| 3등 |
맨 뒤(3번째)의 설정 정보를 1~3 중 무작위 추첨된 3번째 자리의 설정 정보와 자리 교환(자리가 동일하므로 교환 없음)
그 앞(2번째)의 설정 정보를 1~2 중 무작위 추첨된 1번째 자리의 설정 정보와 자리 교환
| 정렬 순위 | 응모자정보 | 가중치 (W) | key | 추첨 설정 정보 (셔플 후) | 결과 |
|---|---|---|---|---|---|
| 1 | 김철수 | 150 | 0.002098 | 2등 | 당첨 |
| 2 | 안성준 | 100 | 0.002877 | 1등 | 당첨 |
| 3 | 김용만 | 160 | 0.003968 | 3등 | 당첨 |
| 4 | 지석진 | 10 | 0.005129 | — | 낙첨 |
| 5 | 이영희 | 200 | 0.010601 | — | 낙첨 |
| 6 | 나유미 | 50 | 0.017832 | — | 낙첨 |
| 7 | 전현무 | 30 | 0.027366 | — | 낙첨 |
- Efraimidis, P. S., & Spirakis, P. G. (2006). Weighted Random Sampling with a Reservoir. Information Processing Letters, 97(5), 181–185.
유니피커 난수 시드와 현장에서 뽑은 공 번호로 추첨난수를 결정하는 추첨입니다.
추첨 관계인이나 응모자가 추첨에 참여하여 더욱 공정한 추첨을 진행할 수 있습니다.
단, 추첨과정을 실시간으로 공개하여 추첨을 진행하는 경우에만 공정성을 보장할 수 있습니다.
응모자의 추첨 난수 = 39540329
유니피커는 아래와 같은 공 번호 입력 공개추첨 로직을 적용한다.
- 응모자마다 유니피커에서 생성한 난수를 할당한다.생성한 난수의 정수부분부터 소수점까지 제거 후 앞 10자리 수(유니피커 난수)를 할당한다.
- 응모자의 유니피커 난수와 공 번호를 곱한다.현장에서 공개적으로 뽑은 공 번호를 사용한다.
- 곱한 값의 마지막 8자리 수를 기준으로 응모자를 정렬한다.
- 정렬한 응모자를 순서대로 당첨 처리한다.
유니피커 기본 추첨 로직은 응모자마다 난수를 부여해 당첨자를 뽑는다. 하지만 PC의 CPU와 메모리 한계로 대량 추첨에는 적합하지 않다.
대량 추첨은 응모자마다 응모번호를 순서대로 부여하고, 컴퓨터 난수를 이용하여 당첨번호를 뽑는 추첨 방식을 사용한다.
공정한 난수를 뽑기 위해 ‘1. 불공정 난수 거부 정책’을 적용하고, 중복 당첨번호를 효율적으로 체크하기 위해 ‘2. Floyd’s Sampling Without Replacement(플로이드의 중복 없는 표본 추출 알고리즘)’를 사용한다.
| 응모번호 | 응모자정보 |
|---|---|
| 1번 | 홍길동 |
| 2번 | 이순신 |
| 3번 | 강감찬 |
| 4번 | 김유신 |
| 5번 | 이성계 |
실제 유니피커에서는 최대 9,007,199,254,740,992(2⁵³)까지 난수를 생성할 수 있다.
<그림 4>의 가정으로 컴퓨터 난수를 뽑아 1명의 당첨자를 결정할 때, 컴퓨터 난수에 따른 당첨번호를 일반적으로 아래와 같이 배치할 수 있다.
| 공정한 난수 범위 ( 응모자 수의 배수 범위만 사용 ) | 불공정 난수 거부 | |||||||||||
| 컴퓨터 난수 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 당첨번호 (당첨자) | 1번 홍길동 | 2번 이순신 | 3번 강감찬 | 4번 김유신 | 5번 이성계 | 1번 홍길동 | 2번 이순신 | 3번 강감찬 | 4번 김유신 | 5번 이성계 | 1번 홍길동 | 2번 이순신 |
예) 컴퓨터가 생성한 난수가 4이면 4번 김유신, 8이면 3번 강감찬이 당첨자로 선정
위와 같이 컴퓨터가 생성한 난수 범위(1~12)의 숫자를 그대로 사용하면, 난수가 11 또는 12가 나올 경우 홍길동과 이순신이 다른 사람보다 당첨 확률이 높아진다.
| 응모번호 | 응모자정보 | 당첨기회 |
|---|---|---|
| 1번 | 홍길동 | 3회 (1, 6, 11) |
| 2번 | 이순신 | 3회 (2, 7, 12) |
| 3번 | 강감찬 | 2회 (3, 8) |
| 4번 | 김유신 | 2회 (4, 9) |
| 5번 | 이성계 | 2회 (5, 10) |
난수 거부
| 응모번호 | 응모자정보 | 최종 당첨기회 |
|---|---|---|
| 1번 | 홍길동 | 2회 (1, 6, |
| 2번 | 이순신 | 2회 (2, 7, |
| 3번 | 강감찬 | 2회 (3, 8) |
| 4번 | 김유신 | 2회 (4, 9) |
| 5번 | 이성계 | 2회 (5, 10) |
공정한 확률을 위해 생성한 컴퓨터 난수가 11 또는 12가 나올 경우, 사용하지 않고 컴퓨터 난수를 다시 생성한다.
즉, 유효한 컴퓨터 난수는 응모자 수의 배수 범위만 사용하고, 초과되는 난수는 거부한다.
이를 ‘불공정 난수 거부 정책’이라 한다.
당첨번호가 중복되지 않도록 하려면 번호를 뽑을 때마다 기존 당첨번호와 중복 여부를 체크해야 한다. 뽑아야 하는 당첨자 수가 매우 많거나 중복이 자주 발생하면 이 체크가 과도하게 반복될 수 있어, 대량 응모자 당첨자 추첨에서는 Floyd’s Sampling Without Replacement를 적용한다.
<그림 4>의 가정으로 컴퓨터 난수를 뽑아 총 3명의 당첨자를 결정할 때, 아래와 같이 중복 추첨을 방지할 수 있다.
| 추첨 | 응모번호 범위 | 결과 | 당첨번호 리스트 |
|---|---|---|---|
| (1) 첫 번째 | 1 ~ 3 | 컴퓨터 난수 11 → 2번 | 2번 |
| (2) 두 번째 (중복 발생) | 1 ~ 4 | 컴퓨터 난수 2 → 2번(중복) → 새로 추가된 4번 당첨 | 2번, 4번 |
| (3) 세 번째 | 1 ~ 5 | 컴퓨터 난수 6 → 1번 | 2번, 4번, 1번 |
첫 번째 추첨 범위 = 총 응모자 수 − 총 당첨자 수 + 1 (=3), 이후 추첨마다 범위가 1씩 늘어난다.
이 로직을 적용하면, 중복 번호가 생겨도 컴퓨터 난수를 다시 생성할 필요가 없어 효율적이다.
1 ~ 3 번까지의 응모자는 3번의 추첨기회를 얻고, 4번 응모자는 2번의 추첨기회, 5번 응모자는 1번의 추첨기회를 얻어 불공정하다고 생각할 수 있으나, 두 번째 추첨에서 중복 당첨자 수가 나올 경우 4번이 당첨번호로 선정되고, 세번째 추첨에서 기존 번호들은 결국 중복될 확률이 높아 5번이 당첨될 확률이 높아져 이 로직을 적용하면 효과적으로 공정하게 중복 추첨을 방지 할 수 있다.
- Robert Floyd’s Tiny and Beautiful Algorithm. nowherenearithaca.com
- A Sample of Brilliance. Fermat’s Library. fermatslibrary.com/s/a-sample-of-brilliance
대량 응모자 당첨자 추첨 로직으로 당첨자를 선정한 후, 각 당첨자에게 다시 난수를 부여하고 추첨 시 순번을 배정한다.
<그림5>의 가정으로 순번 배정을 진행하면 다음과 같다.
유니피커 ‘시드 발급 서버’에서 발급된 최초 ‘시드’ 값은 161925012407392416이라고 가정한다.
| 당첨자 정보 | 난수 |
|---|---|
| 2번 이순신 | 0.677889 |
| 4번 김유신 | 0.321264 |
| 1번 홍길동 | 0.473173 |
정렬
| 순번 | 난수 | 당첨자 정보 |
|---|---|---|
| 1 | 0.677889 | 2번 이순신 |
| 2 | 0.473173 | 1번 홍길동 |
| 3 | 0.321264 | 4번 김유신 |
