Unipicker추첨 백서
추첨로직

유니피커 추첨로직

유니피커의 주요 추첨 로직을 확인할 수 있어요.

기본 추첨 로직

유니피커는 아래와 같은 로직으로 당첨자를 선정한다.

  1. ‘시드 발급 서버’에서 ‘시드’를 발급받는다.‘시드’를 ‘난수 생성 알고리즘’에 입력값으로 전달한다.
  2. 응모자마다 난수를 할당한다.
  3. 난수를 기준으로 응모자를 정렬한다.
  4. 그룹 추첨 유형은 추첨 설정 정보에도 난수를 할당한다.그룹 추첨이란 그룹별로 당첨자를 뽑는 추첨을 말한다. 이러한 유형의 추첨에는 그룹정보(등수나 경품명, 아파트 동/호수 같은 당첨자를 구분하는 정보)별로 당첨자 수를 정하는 추첨 설정 정보를 입력해야 한다. 유니피커는 응모자뿐만 아니라 추첨 설정 정보에도 난수를 할당한다.
  5. 난수를 기준으로 추첨설정 정보를 정렬한다.
  6. 정렬한 응모자를 순서대로 뽑아 정렬한 추첨 설정 정보에 할당(당첨)한다.
* 응모자(또는 추첨설정) 정보를 정렬할 때, 응모자마다 할당된 난수를 기준으로 정렬하는데 만약, 발급받은 ‘시드’가 홀수이면 오름차순으로, 짝수이면 내림차순으로 정렬한다. 이는 두 명 이상의 응모자에게 동일한 난수가 할당되었을 경우 입력자료에 우선 등록된 응모자가 당첨 우선순위를 갖는 것을 방지하기 위함이다.
< 그림 1 > 동/호수 당첨자 추첨, 난수 할당 및 당첨자 선정 예시
시드 : 6829955767104992498
응모자마다 난수 할당
응모자정보난수
홍길동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(시드) 방식² 중 하나를 선택하여 이용할 수 있다.

1. 가중치 구간 추첨 방식

유니피커는 가중치 당첨자 추첨 로직 중 가중치 구간 추첨을 다음과 같은 방식으로 적용한다.

  1. 응모자 리스트를 무작위로 섞는다.응모자 리스트를 피셔-예이츠(Fisher-Yates) 셔플 알고리즘³을 이용하여 무작위로 섞는다. 셔플된 순서에 따라 응모자가 배치되고, 각 응모자는 가중치에 비례하는 크기의 당첨 구간을 갖는다.
  2. 추첨 설정 정보를 무작위로 섞는다.추첨 설정 정보를 피셔-예이츠 셔플 알고리즘³을 이용하여 무작위로 섞는다.
  3. ‘당첨 기준값’을 생성한다.(1) ‘당첨 기준값’의 범위는 1부터 ‘응모자 가중치 총합’까지이다. (2) 해당 범위 내에서 난수를 생성하여 ‘당첨 기준값’으로 사용한다. 예) ‘응모자 가중치 총합’이 600일 때, 난수 생성 범위는 1부터 600까지이다.
  4. 당첨자를 선정한다.응모자 리스트를 순서대로 순회하여 ‘당첨 기준값’이 특정 응모자의 ‘당첨 구간’에 포함되는 경우 해당 응모자를 당첨자로 선정한다.
  5. 당첨자를 추첨 설정 정보에 할당한다.선정된 당첨자를 셔플된 추첨 설정 정보에 순서대로 할당한다. 모든 추첨 설정 정보에 당첨자가 할당될 때까지 3부터 6까지의 과정을 반복한다.
  6. 당첨자로 선정된 응모자는 이후 추첨 대상에서 제외한다.남은 응모자를 기준으로 당첨 구간을 다시 설정하고, 응모자 가중치 총합을 재계산한다. 예) 가중치 총합이 600이고 당첨자의 가중치가 160일 때, 다음 범위는 1부터 440까지이다.
< 그림 2 > 가중치 구간 추첨, 당첨자 선정 예시
응모자 리스트를 피셔-예이츠 셔플
응모자 리스트 (셔플 전)
응모자정보가중치 (W)
김철수150
나유미50
지석진10
이영희200
김용만160
안성준100
전현무30
피셔-예이츠
셔플
응모자 리스트 (셔플 후)
응모자정보가중치 (W)
안성준100
이영희200
김철수150
나유미50
전현무30
지석진10
김용만160
피셔-예이츠 셔플 — 맨 끝 자리부터 셔플을 진행한다.
맨 끝(7번째) 자리 응모자를 1~7 중 무작위 추첨된 5번째 자리의 응모자와 자리 교환 (전현무 ↔ 김용만)
그 앞(6번째) 자리 응모자를 1~6 중 무작위 추첨된 3번째 자리의 응모자와 자리 교환 (안성준 ↔ 지석진)
추첨 설정 정보를 피셔-예이츠(Fisher-Yates) 셔플
추첨 설정 정보 (셔플 전)
추첨 설정 정보
1등
2등
3등
피셔-예이츠
셔플
추첨 설정 정보 (셔플 후)
추첨 설정 정보
2등
1등
3등
피셔-예이츠 셔플 — 맨 뒤 설정부터 셔플을 진행한다.
맨 뒤(3번째)의 설정 정보를 1~3 중 무작위 추첨된 3번째 자리의 설정 정보와 자리 교환(자리가 동일하므로 교환 없음)
그 앞(2번째)의 설정 정보를 1~2 중 무작위 추첨된 1번째 자리의 설정 정보와 자리 교환
‘당첨 기준값’ 결정
난수 생성 범위
1 부터 700 까지
응모자가중치총합
당첨 기준값
난수 생성
생성된 ‘당첨 기준값’
412
당첨자 선정
안성준100
이영희200
김철수150
나유미50
1
101
301
451
501 ~ 700
당첨기준값 412
응모자정보가중치당첨 구간
안성준1001 ~ 100
이영희200101 ~ 300
당첨자 선정김철수150301 ~ 450 412 당첨기준값
나유미50451 ~ 500
김용만160541 ~ 700
추첨 설정 정보에 당첨자를 할당(당첨)
선정된 당첨자
첫번째
김철수
두번째
김용만
세번째
나유미
할당(당첨)
추첨 설정 정보
2등
1등
3등
당첨자를 다음 추첨 대상에서 제외
안성준100
이영희200
나유미50
1
101
301
351 ~ 550

김철수 제외 후 가중치 총합 700 → 550으로 변경, 남은 응모자의 당첨 구간이 재계산된다.

¹ SHA-256(시드|N) 방식 — SHA-256 해시 함수를 이용하여 각 난수를 독립적으로 생성한다. 결과의 재현성과 검증 가능성을 중요하게 고려하는 추첨에 적합하다.
² xoshiro(시드) 방식 — 시드값을 기반으로 연속적인 난수열을 생성한다. 처리 속도가 빠르며 대규모 추첨에 적합하다.
³ 피셔-예이츠(Fisher-Yates) 셔플 알고리즘 — 응모자 리스트의 무작위 배치를 위해 사용하였다. 모든 가능한 순열이 동일한 확률로 생성되도록 보장하는 무편향(Unbiased) 셔플 알고리즘으로, 통계학 및 컴퓨터 과학 분야에서 널리 사용되고 있다.
menu_book참고문헌
2. 가중치 키 추첨 방식

유니피커는 가중치 당첨자 추첨 로직 중 가중치 키 추첨을 다음과 같은 방식으로 적용한다.

  1. 응모자마다 난수를 할당한다.응모자 전원에게 각각 0~1 사이의 난수(u)를 하나씩 발급한다.
  2. 응모자별 가중치를 반영한 Key값을 생성한다.발급된 난수(u)와 응모자의 가중치(w)를 이용하여 각 응모자의 키 값을 계산한다. 가중치가 클수록 더 작은 Key 값이 생성될 가능성이 높으며, Key 값이 작은 순서대로 당첨 우선순위가 결정된다.
  3. 응모자 리스트를 계산된 Key 값을 기준으로 오름차순 정렬한다.
  4. 추첨 설정 정보를 무작위로 섞는다.추첨 설정 정보를 피셔-예이츠 셔플 알고리즘¹을 이용하여 무작위로 섞는다.
  5. Key 값 순으로 정렬된 응모자를 순서대로 셔플된 추첨 설정 정보에 할당(당첨)한다.
key = −ln(u) / wu : 0~1 사이의 난수 · w : 응모자의 가중치 · −ln(u)는 난수를 가중치 적용에 적합한 값으로 변환하여 가중치에 비례한 당첨 확률을 구현한다.
※ Efraimidis–Spirakis(2006)가 제안한 가중 표본추출 알고리즘을 기반으로 한다.
< 그림 3 > 가중치 키 추첨, 당첨자 선정 예시
응모자마다 난수를 할당하고 응모자별 키(key) 값을 계산
응모자정보가중치 (W)난수 (U)−ln(u)key=−ln(u)/w
김철수1500.730.31470.002098
나유미500.410.89160.017832
지석진100.950.05130.005129
이영희2000.122.12030.010601
김용만1600.530.63490.003968
안성준1000.750.28770.002877
전현무300.440.82100.027366
응모자 리스트를 계산된 키 값을 기준으로 오름차순 정렬
정렬 순위응모자정보가중치 (W)난수 (U)−ln(u)key=−ln(u)/w
1김철수1500.730.31470.002098
2안성준1000.750.28770.002877
3김용만1600.530.63490.003968
4지석진100.950.05130.005129
5이영희2000.122.12030.010601
6나유미500.410.89160.017832
7전현무300.440.82100.027366
추첨 설정 정보를 피셔-예이츠(Fisher-Yates) 셔플
추첨 설정 정보 (셔플 전)
추첨 설정 정보
1등
2등
3등
피셔-예이츠
셔플
추첨 설정 정보 (셔플 후)
추첨 설정 정보
2등
1등
3등
피셔-예이츠 셔플 — 맨 뒤 설정부터 셔플을 진행한다.
맨 뒤(3번째)의 설정 정보를 1~3 중 무작위 추첨된 3번째 자리의 설정 정보와 자리 교환(자리가 동일하므로 교환 없음)
그 앞(2번째)의 설정 정보를 1~2 중 무작위 추첨된 1번째 자리의 설정 정보와 자리 교환
Key 값 순으로 셔플된 추첨 설정 정보에 할당(당첨)
정렬 순위응모자정보가중치 (W)key추첨 설정 정보 (셔플 후)결과
1김철수1500.0020982등당첨
2안성준1000.0028771등당첨
3김용만1600.0039683등당첨
4지석진100.005129낙첨
5이영희2000.010601낙첨
6나유미500.017832낙첨
7전현무300.027366낙첨
menu_book참고문헌
  • Efraimidis, P. S., & Spirakis, P. G. (2006). Weighted Random Sampling with a Reservoir. Information Processing Letters, 97(5), 181–185.
공 번호 입력 공개추첨 로직

유니피커 난수 시드와 현장에서 뽑은 공 번호로 추첨난수를 결정하는 추첨입니다.
추첨 관계인이나 응모자가 추첨에 참여하여 더욱 공정한 추첨을 진행할 수 있습니다.
단, 추첨과정을 실시간으로 공개하여 추첨을 진행하는 경우에만 공정성을 보장할 수 있습니다.

유니피커 생성 난수
2498753211
×
현장에서 뽑은 공 번호
4
1
3
9
=
계산결과의 끝 8자리를 응모자의 추첨난수로 사용
10342339540329

응모자의 추첨 난수 = 39540329

유니피커는 아래와 같은 공 번호 입력 공개추첨 로직을 적용한다.

  1. 응모자마다 유니피커에서 생성한 난수를 할당한다.생성한 난수의 정수부분부터 소수점까지 제거 후 앞 10자리 수(유니피커 난수)를 할당한다.
  2. 응모자의 유니피커 난수와 공 번호를 곱한다.현장에서 공개적으로 뽑은 공 번호를 사용한다.
  3. 곱한 값의 마지막 8자리 수를 기준으로 응모자를 정렬한다.
  4. 정렬한 응모자를 순서대로 당첨 처리한다.
* 응모자 정보를 정렬할 때, 응모자마다 할당된 당첨 난수를 기준으로 정렬하는데 만약, 입력한 공 번호가 ‘홀수’이면 ‘오름차순’으로, ‘짝수’이면 ‘내림차순’으로 정렬한다. 이는 두 명 이상의 응모자에게 동일한 난수가 할당되었을 경우 입력 자료에 우선 등록된 응모자가 당첨 우선순위를 갖는 것을 방지하기 위함이다.
* 공 번호 입력 공개추첨은 타 추첨과 다르게 추첨 설정 정보를 무작위로 섞지 않는다. 이는 투명하게 공개된 응모자 난수의 정렬 순으로 당첨자를 결정하기 위한 정책이다.
대량 응모자 당첨자 추첨 로직

유니피커 기본 추첨 로직은 응모자마다 난수를 부여해 당첨자를 뽑는다. 하지만 PC의 CPU와 메모리 한계로 대량 추첨에는 적합하지 않다.
대량 추첨은 응모자마다 응모번호를 순서대로 부여하고, 컴퓨터 난수를 이용하여 당첨번호를 뽑는 추첨 방식을 사용한다.
공정한 난수를 뽑기 위해 ‘1. 불공정 난수 거부 정책’을 적용하고, 중복 당첨번호를 효율적으로 체크하기 위해 ‘2. Floyd’s Sampling Without Replacement(플로이드의 중복 없는 표본 추출 알고리즘)’를 사용한다.

< 그림 4 > 대량 응모자 당첨자 추첨, 추첨 정보 예시
(1) 컴퓨터가 만드는 난수는 1부터 12 사이의 숫자 12개로 고정되어 있다고 가정한다.
(2) 총 응모자 수 : 5명
응모번호응모자정보
1번홍길동
2번이순신
3번강감찬
4번김유신
5번이성계
※ 본 예시는 추첨 로직을 쉽게 이해할 수 있도록 난수 범위를 1~12로 가정하였다.
실제 유니피커에서는 최대 9,007,199,254,740,992(2⁵³)까지 난수를 생성할 수 있다.
1. 불공정 난수 거부 정책

<그림 4>의 가정으로 컴퓨터 난수를 뽑아 1명의 당첨자를 결정할 때, 컴퓨터 난수에 따른 당첨번호를 일반적으로 아래와 같이 배치할 수 있다.

공정한 난수 범위 ( 응모자 수의 배수 범위만 사용 )불공정
난수 거부
컴퓨터 난수123456789101112
당첨번호
(당첨자)
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, 11)
2번이순신2회 (2, 7, 12)
3번강감찬2회 (3, 8)
4번김유신2회 (4, 9)
5번이성계2회 (5, 10)
‘불공정 난수 거부 정책’으로 모두 동일한 당첨 기회 부여난수 범위(1~12)를 그대로 사용하면 11·12가 나올 때 홍길동·이순신이 다른 사람보다 당첨 확률이 높아진다. 불공정 난수 거부 정책을 적용하면 1~3번은 3회(1·6·11 / 2·7·12), 4·5번은 2회(4·9 / 5·10)로, 유효 범위(1~10) 안에서 모두 동일한 당첨 기회를 갖는다.

공정한 확률을 위해 생성한 컴퓨터 난수가 11 또는 12가 나올 경우, 사용하지 않고 컴퓨터 난수를 다시 생성한다.
즉, 유효한 컴퓨터 난수는 응모자 수의 배수 범위만 사용하고, 초과되는 난수는 거부한다.
이를 ‘불공정 난수 거부 정책’이라 한다.

※ 컴퓨터 난수별 매칭되는 당첨번호를 수식으로 표현하면 아래와 같다.
당첨번호 = 컴퓨터 난수 % 응모자 수
( 컴퓨터 난수를 응모자 수로 나눈 나머지 )
※ 본 예시는 추첨 로직을 쉽게 이해할 수 있도록 작성되었다.
실제 구현식은 당첨번호 = (컴퓨터 난수 % 응모자 수) + 1이며, 당첨번호를 1부터 시작하기 위해 1을 더한다.
2. Floyd’s Sampling Without Replacement (플로이드의 중복 없는 표본 추출 알고리즘)

당첨번호가 중복되지 않도록 하려면 번호를 뽑을 때마다 기존 당첨번호와 중복 여부를 체크해야 한다. 뽑아야 하는 당첨자 수가 매우 많거나 중복이 자주 발생하면 이 체크가 과도하게 반복될 수 있어, 대량 응모자 당첨자 추첨에서는 Floyd’s Sampling Without Replacement를 적용한다.

<그림 4>의 가정으로 컴퓨터 난수를 뽑아 총 3명의 당첨자를 결정할 때, 아래와 같이 중복 추첨을 방지할 수 있다.

< 그림 5 > 대량 응모자 다수 당첨자 추첨 예시
※ 각 추첨 별 응모자 리스트
첫 번째 추첨 범위
두 번째 추첨 범위
세 번째 추첨 범위
1번홍길동
2번이순신
3번강감찬
+
4번김유신
+
5번이성계
※ 각 추첨 별 응모번호 범위와 결과
추첨응모번호 범위결과당첨번호 리스트
(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번이 당첨될 확률이 높아져 이 로직을 적용하면 효과적으로 공정하게 중복 추첨을 방지 할 수 있다.

“앞사람은 일찍 기회를 갖지만 밀릴 위험도 크고, 뒷사람은 늦게 들어오지만 밀어낼 기회가 크기 때문에 전체적으로는 모두에게 똑같은 당첨 확률이 되도록 설계된 알고리즘”이다.
menu_book참고문헌
대량 응모자 순번 배정 추첨 로직

대량 응모자 당첨자 추첨 로직으로 당첨자를 선정한 후, 각 당첨자에게 다시 난수를 부여하고 추첨 시 순번을 배정한다.

<그림5>의 가정으로 순번 배정을 진행하면 다음과 같다.
유니피커 ‘시드 발급 서버’에서 발급된 최초 ‘시드’ 값은 161925012407392416이라고 가정한다.

당첨자마다 난수 할당
당첨자 정보난수
2번 이순신0.677889
4번 김유신0.321264
1번 홍길동0.473173
난수
정렬
순번 배정 결과
순번난수당첨자 정보
10.6778892번 이순신
20.4731731번 홍길동
30.3212644번 김유신
난수정렬
시드 값이 짝수이므로 난수를 기준으로 내림차순 정렬
※ 시드 값이 홀수이면 오름차순 정렬