당신의 점심 룰렛이 공정하지 않은 이유

"이상하게 점심 룰렛 돌리면 A랑 B가 맨날 같이 걸리는 것 같은데..."

회사에서 점심 메뉴 룰렛을 몇 번 돌리다 보니, 슬랙에 이런 의문이 올라왔다. 처음엔 "그냥 운이겠지"라고 넘겼는데, 몇 번 더 돌려보니 정말 특정 사람들끼리 자주 뭉쳐 나온다. 셔플 알고리즘 자체에 문제가 있는 건 아닐까?

궁금해서 코드를 뜯어봤다. 범인은 array.sort(() => Math.random() - 0.5). 간단해 보이지만, 이 한 줄이 편향의 원인이었다.

Mike Bostock의 Will It Shuffle?에서 영감을 받아, 본 글에서는 D3.js와 React로 셔플 알고리즘의 편향을 직접 시각화해본다. 잘못된 셔플이 왜 문제인지, 그리고 Fisher-Yates가 왜 공정한지 눈으로 확인해보자.

셔플의 공정성

완벽한 셔플이라면 모든 요소가 모든 위치에 동일한 확률로 배치되어야 한다. $N$개 요소가 있다면 특정 요소가 특정 위치에 올 확률은 정확히 $\frac{1}{N}$이다.

이 조건을 만족하지 못하면 편향(Bias)이 있다고 한다. 예를 들어 $N=3$이면, A가 0/1/2번째에 있을 확률이 모두 $\frac{1}{3}$이어야 한다. Matrix Diagram에서는 대각선이 진할수록 '원래 자리 근처에 남는 경향'이 강하다는 뜻이다. 반대로 전체가 고르게 회색이면 각 위치 확률이 거의 균일하다는 뜻이다. 특정 행/열이 진하면 특정 원소/위치로 쏠림이 있는 것이다. 이 가이드만 기억하고 아래 시각화를 보면 패턴을 훨씬 빨리 읽을 수 있다.

시각화: Matrix Diagram

아래 시각화는 셔플을 수천 번 돌리고 결과를 집계한다. 행은 원래 위치, 열은 셔플 후 위치다. 균일한 회색이면 공정하고, 패턴이 보이면 편향이 있다.

드롭다운에서 알고리즘을 바꿔가며 비교해보자. 어떤 알고리즘이 공정하고, 어떤 알고리즘이 편향되어 있는지 눈으로 확인할 수 있다.

1. Random Comparator (나쁜 예)

가장 흔한 실수는 array.sort(() => Math.random() - 0.5) 코드다.

// ❌ 쓰지 말자
function randomComparatorShuffle(array) {
  return array.sort(() => Math.random() - 0.5);
}

시각화에서 Random Comparator를 선택해보자. 가장자리에 얼룩이 묻은 듯한 불규칙한 패턴이 나타난다. 특히 배열의 앞부분과 끝부분 요소들이 특정 위치로 쏠리는 경향을 볼 수 있다.

왜 실패하는가

sort는 일관된 비교 함수(특히 추이성)를 전제로 동작한다. 그런데 () => Math.random() - 0.5는 비교할 때마다 결과가 바뀌어, $a \lt b$, $b \lt c$인데도 $c \lt a$ 같은 모순(비추이성)이 생길 수 있다. 추이성이 깨지면 정렬 과정이 구현(엔진/알고리즘)에 따라 달라져서 편향된 분포가 나온다.

결국 sort(() => Math.random() - 0.5)는 겉보기엔 섞이는 것 같아도, 공정한 셔플이 아니다.

2. Naive Swap (나쁜 예)

또 다른 실수는 모든 요소를 임의의 위치와 교환하는 방식이다.

// ❌ 미묘하게 편향된다
function naiveSwapShuffle(array) {
  for (let i = 0; i < array.length; i++) {
    const j = randomInt(0, array.length - 1); // 전체 배열에서 아무 위치나
    [array[i], array[j]] = [array[j], array[i]]; // swap
  }
}

겉보기에는 Fisher–Yates와 비슷하다. "모든 i에 대해 임의의 j를 골라 swap한다"는 말이 그럴싸해 보여서 더 위험하다.

핵심 문제는 무작위로 뽑는 단위(선택 경로)가 원하는 결과(순열)와 1:1 대응이 아니라는 점이다. 여러 경로가 같은 순열로 압축되는데, 그 압축 비율이 순열마다 다르기 때문에 분포가 찌그러진다.

이런 편향이 누적되어 행렬 다이어그램에서 대각선(원래 위치 근처)이 상대적으로 두드러지게 된다.

3. Fisher-Yates Shuffle (좋은 예)

올바른 방법은 Fisher-Yates(또는 Knuth) 셔플이다.

// ✅ 공정한 셔플
function fisherYatesShuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = randomInt(0, i); // 아직 섞지 않은 구간에서만 선택
    [array[i], array[j]] = [array[j], array[i]]; // swap
  }
}

이 알고리즘은 수학적으로 완벽하게 공정하다. 시각화에서 Fisher-Yates를 선택하면 전체가 균일한 회색 노이즈로 채워진다.

결론

셔플 알고리즘의 작은 차이가 결과 분포에 큰 영향을 준다. 게임, 암호화, 샘플링처럼 무작위성이 중요한 곳에서는 반드시 검증된 알고리즘을 써야 한다.

핵심 규칙:

1. array.sort(() => Math.random() - 0.5) 쓰지 말자. 편향이 생긴다.
2. Fisher-Yates를 쓰자. 대부분의 언어와 라이브러리에 이미 구현되어 있다.

실전에서 쓰기

직접 구현할 필요 없이, 검증된 라이브러리를 사용하면 된다.

// JavaScript: Lodash 사용
import { shuffle } from 'lodash';
const shuffled = shuffle([1, 2, 3, 4, 5]);

# Python: 내장 random 모듈 (in-place Fisher-Yates)
import random
arr = [1, 2, 3, 4, 5]
random.shuffle(arr)

// Go: math/rand 패키지
import "math/rand"
rand.Shuffle(len(arr), func(i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
})