알고리즘 · LESSON 1
난수로 줄세우기
기본추첨응모자마다 난수를 하나씩 나눠주고, 그 난수 순서대로 줄을 세워 당첨자를 정하는 방식이에요.
핵심은 둘 — ① 줄 세우는 방향(오름/내림)은 '시드'가 정해요. ② 위에서부터 뽑되 이미 당첨된 사람은 건너뛰어요.
개념
난수를 나눠주고 줄 세우기
응모자(또는 응모 한 건)마다 난수 하나를 할당해요. 그다음 이 난수를 기준으로 전체를 한 줄로 정렬하면, 줄의 앞쪽이 곧 당첨 우선순위가 돼요.
난수는 앞에서 배운 안전한 난수로 만들어요. 그래서 같은 시드면 누구나 똑같은 줄을 다시 만들어 검증할 수 있어요.
정렬 방향
방향은 '시드'가 정해요 — 홀수 오름 · 짝수 내림
최초 입력된 시드 값이 홀수이면 오름차순(작은 난수가 앞), 짝수이면 내림차순(큰 난수가 앞)으로 줄을 세워요. 방향까지 시드로 고정되니, 추첨자가 방향을 임의로 고를 수 없어요.
홀수 시드오름차순 ↑ · 난수가 작은 순서대로 앞줄
짝수 시드내림차순 ↓ · 난수가 큰 순서대로 앞줄
중복당첨 막기
이미 당첨된 사람은 건너뛰어요
대량 응모에서는 한 사람이 여러 번 응모할 수 있어, 줄에 같은 사람이 여러 번 나올 수 있어요. 줄의 앞에서부터 차례로 당첨자를 확인하다가, 이미 당첨된 사람이 또 나오면 그 건은 패스하고 다음으로 넘어가요.
왜 이렇게? 다시 뽑지 않고 패스만 하면 되니 빠르고, 필요한 수만큼 중복 없이 당첨자가 채워져요.
실험
직접 줄 세워보기 (5명 · 당첨 3명)
A·B·C·D·E의 응모예요. A·B는 2번씩 응모했어요. 시드를 바꿔 오름차순/내림차순 정렬방향이 어떻게 달라지는지, 중복이 어떻게 패스되는지 확인해봐요. (이 실험에서 최초 시드는 정렬방향만 결정하고, 난수는 매번 새로 뽑혀요.)
최초 시드
난수를 할당해 줄 세운 결과
시드가 홀수면 위쪽이 작은 난수, 짝수면 위쪽이 큰 난수예요. 위에서부터 뽑다가 중복은 패스되는 걸 볼 수 있어요.