"무작위 정렬" 버튼을 눌렀을 때, 결과는 정말 무작위일까요? 많은 사람들이 난수 함수만 호출하면 공정한 무작위 순열을 얻을 수 있다고 생각합니다. 하지만 실제로는 잘못된 구현 방식이 특정 순열을 더 자주 출현하게 만드는 숨겨진 편향을 일으킵니다. 이 글에서는 올바른 무작위 셔플 알고리즘인 Fisher-Yates Shuffle의 원리를 설명합니다.
1. "공정한 무작위 순열"이란 무엇인가?
3개의 요소 [A, B, C]가 있다면, 가능한 모든 순열은 3! = 6가지입니다:
ABC ACB BAC BCA CAB CBA"공정한 셔플"은 이 6가지 순열이 각각 1/6 ≈ 16.67%의 확률로 나타나는 것을 의미합니다. 어떤 구현에서 ABC가 20%의 확률로 나타나고 나머지가 16%라면, 그것은 "무작위처럼 보이지만" 통계적으로 편향된 셔플입니다.
2. 흔한 함정: sort() + Math.random()
많은 개발자들이 작성해본 코드 (JavaScript):
// 흔하지만 편향이 있는 방법
array.sort(() => Math.random() - 0.5);합리적으로 보이지만 실제로는 심각한 편향 문제가 있습니다:
- 정렬 알고리즘은 일관된 비교를 전제로 한다: 퀵소트, 병합 정렬 등은 동일한 두 요소를 여러 번 비교할 수 있으며, 매번 동일한 결과를 기대합니다. 무작위 비교 함수는 매 호출마다 결과가 뒤집힐 수 있어 알고리즘이 예기치 않은 경로를 취하게 됩니다.
- 수학적으로 균일 분포를 보장할 수 없다: 비교 정렬의 시간 복잡도는 O(n log n)으로, n log n번의 비교만 수행합니다. n개 요소의 순열은 n!가지인데, n!이 비교 횟수로 구분할 수 있는 상태 수보다 훨씬 크면 일부 순열이 "합쳐져서" 더 높은 확률로 출현합니다.
[1,2,3]에 sort+random을 100만 번 실행하면, 일부 순열이 균등한 16.67%가 아닌 약 20%로 출현하는 것을 확인할 수 있습니다. 편향이 작더라도 공정성이 필요한 추첨에서는 허용할 수 없습니다.
3. Fisher-Yates 알고리즘의 원리
Fisher-Yates Shuffle(현대 버전은 Knuth Shuffle이라고도 함)은 1938년 Ronald Fisher와 Frank Yates가 고안하고, Donald Knuth가 《컴퓨터 프로그래밍의 예술》에서 현대적인 형태로 발전시켰습니다.
알고리즘 단계 (n개 요소 배열):
- 마지막 요소(인덱스 n-1)에서 시작하여 인덱스 1까지 역방향으로 순회합니다.
- 현재 인덱스
i에 대해[0, i](양 끝 포함) 범위에서 무작위로 인덱스j를 선택합니다. array[i]와array[j]를 교환합니다.i-1로 이동하여i = 1이 될 때까지 반복합니다.
// Fisher-Yates Shuffle (JavaScript 올바른 구현)
function shuffle(array) {
const a = [...array]; // 원본 배열 수정 안 함
for (let i = a.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[a[i], a[j]] = [a[j], a[i]]; // 교환
}
return a;
}4. Fisher-Yates가 균일 분포를 보장하는 이유
[A, B, C]를 예로 확률을 단계별로 분석합니다:
| 단계 | 작업 | 확률 |
|---|---|---|
| i=2 | [0,1,2]에서 j 선택 — 3번째 위치의 요소 결정 | 각 1/3 |
| i=1 | [0,1]에서 j 선택 — 2번째 위치의 요소 결정 | 각 1/2 |
| i=0 | 1번째 위치는 남은 요소로 확정 | 1 |
임의의 특정 순열이 출현할 확률:
P(특정 순열) = 1/3 × 1/2 × 1 = 1/6수학적으로 완전히 균일합니다. n개 요소에 대해 각 순열의 출현 확률은 정확히 1/n!입니다 (난수 함수 자체가 균일 분포라는 전제 하에).
5. 그룹화 구현: 셔플에서 배분으로
"무작위 그룹화"는 "셔플 + 균등 배분"의 두 단계입니다:
function randomGroup(names, groupCount) {
const shuffled = shuffle(names); // 1단계: Fisher-Yates 셔플
const groups = Array.from({ length: groupCount }, () => []);
shuffled.forEach((name, i) => {
groups[i % groupCount].push(name); // 2단계: 순환 배분
});
return groups;
}순환 배분(i % groupCount)으로 각 그룹의 인원 차이는 최대 1명입니다. 10명을 3그룹으로 나누면 4·3·3명이 되며, 4·4·2 같은 불균등한 결과는 발생하지 않습니다.
6. 흔한 실수 정리
| 실수 | 문제 | 올바른 방법 |
|---|---|---|
| array.sort(() => Math.random() - 0.5) | 통계적 편향 | Fisher-Yates 사용 |
| 각 요소에 난수 키를 할당 후 정렬 | 이론상 맞지만 O(n log n) | Fisher-Yates는 O(n) |
| 처음 k개만 무작위로 선택 | 완전한 셔플이 아님 | Fisher-Yates 처음 k번 = 비복원 추출 |
| 같은 위치를 여러 번 무작위 교환 | 교환 확률이 불균일 | 각 위치는 한 번만 교환 |
7. 요약
셔플은 단순해 보이지만 "무작위처럼 보이는 것"과 "통계적으로 균일한 것"은 다릅니다. Fisher-Yates 알고리즘은 O(n) 시간 복잡도와 수학적 균일성 보장을 겸비하여, 공정성이 중요한 모든 상황에서 표준 선택이 되었습니다.
직접 무작위 그룹화를 체험하고 싶다면 이 사이트의 목록 그룹화 도구를 이용해 보세요. 이름을 입력하면 공정한 셔플과 그룹 분배가 즉시 이루어집니다.