피셔-예이츠 셔플

업데이트 2026-07-09

피셔-예이츠 셔플(Fisher–Yates shuffle)은 유한한 개수의 항목으로 구성된 수열을 무작위 순서로 재배열하는 알고리즘이다. 이 알고리즘은 모든 가능한 순열이 동일한 확률로 생성되도록 보장하는 편향되지 않은(unbiased) 무작위 순열을 생성한다. 크누스 셔플(Knuth shuffle)이라고도 불린다.

역사

이 알고리즘은 1938년 통계학자 로널드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates)가 저서 《Statistical Tables for Biological, Agricultural and Medical Research》에서 연필과 종이를 사용한 수작업용 방법으로 처음 제안하였다. 당시에는 난수표를 이용하여 무작위성을 확보하였다.

1964년 리처드 더스텐펠드(Richard Durstenfeld)가 컴퓨터 구현에 적합한 형태로 알고리즘을 개선하였으며, 이후 도널드 커누스(Donald Knuth)가 《The Art of Computer Programming》에서 "알고리즘 P(Shuffling)"라는 이름으로 소개하면서 널리 알려졌다.

알고리즘의 동작

원전(오리지널) 방식

피셔와 예이츠가 제시한 원래 방식은 다음과 같다.

1부터 N까지의 숫자를 적는다.
아직 지워지지 않은 숫자의 개수(포함) 사이에서 임의의 수 k를 선택한다.
낮은 쪽부터 세어 아직 지워지지 않은 k번째 숫자를 지우고, 별도의 리스트 끝에 기록한다.
모든 숫자가 지워질 때까지 2단계부터 반복한다.
3단계에서 기록된 숫자들의 순서가 원래 숫자들의 무작위 순열이 된다.

이 방식은 시간 복잡도가 O(n²)로, 컴퓨터에서 구현할 경우 남은 숫자를 세는 데 불필요한 시간이 소요된다.

현대(더스텐펠드) 방식

더스텐펠드가 고안한 현대적 방식은 제자리(in-place)에서 동작하며, 시간 복잡도가 O(n)으로 최적화되었다. 알고리즘은 다음과 같다.

for i from n-1 down to 1 do
    j ← random integer such that 0 ≤ j ≤ i
    swap A[i] with A[j]

구체적인 동작 과정:

배열의 마지막 인덱스(i = n-1)부터 시작하여 i = 1까지 감소시키며 반복한다.
각 단계에서 0 이상 i 이하의 범위에서 무작위 정수 j를 선택한다.
A[i]와 A[j]의 값을 교환(swap)한다.

이 방식은 선택된 요소를 배열 끝으로 이동시키고, 이미 처리된 요소는 더 이상 건드리지 않음으로써 O(n) 시간에 셔플을 완료한다. 별도의 추가 메모리가 필요하지 않으며(공간 복잡도 O(1)), 제자리에서 동작한다.

반대 방향 셔플

배열을 낮은 인덱스에서 높은 인덱스 방향으로 셔플하는 동등한 버전도 존재한다.

for i from 0 to n-2 do
    j ← random integer such that i ≤ j ≤ n-1
    swap A[i] with A[j]

수학적 정당성

피셔-예이츠 셔플은 n개의 원소에 대해 n!개의 가능한 순열 중 정확히 하나를 균등한 확률(1/n!)로 생성한다. 각 단계에서 선택된 인덱스가 가능한 범위 내에서 균등하게 선택되며, 이후 단계의 선택에 영향을 미치지 않기 때문에 조건부 확률에 따라 모든 순열이 동일한 확률로 생성됨이 증명된다.

특성

시간 복잡도: O(n)
공간 복잡도: O(1) (제자리 알고리즘)
편향성: 모든 순열이 균등한 확률로 생성됨 (무편향)
점근적 최적성: 시간 및 공간 복잡도 측면에서 이론적으로 최적

구현상의 주의점

인덱스 범위 오류

무작위 인덱스 j를 i보다 큰 범위에서 선택하거나, 반대로 i보다 항상 작게 선택(i 미만)하면 순열 분포가 왜곡된다. 특히 j를 항상 i보다 작게 선택할 경우 사톨로 알고리즘(Sattolo's algorithm)이 되어 단일 사이클로 구성된 순열만 생성되며, 어떤 요소도 원래 위치에 도달할 수 없게 된다.

모듈로 편향(Modulo Bias)

난수 생성기의 출력 범위가 원하는 범위로 균등하게 나누어지지 않을 경우, 모듈로 연산을 사용하면 특정 값이 더 자주 선택되는 편향이 발생할 수 있다. 이를 해결하기 위해서는 범위를 벗어난 값을 버리고 다시 시도하는 방법(rejection sampling)을 사용해야 한다.

의사 난수 생성기의 한계

의사 난수 생성기(PRNG)를 사용할 경우, 생성기의 내부 상태 수가 가능한 순열의 수보다 충분히 커야 한다. 예를 들어 32비트 내부 상태를 가진 PRNG는 약 2³²개의 서로 다른 순열만 생성할 수 있으므로, 52장의 카드 덱(52! ≈ 2²²⁵·⁶)의 모든 순열을 생성하는 것은 불가능하다.

변형 알고리즘

사톨로 알고리즘(Sattolo's algorithm)

1986년 산드라 사톨로(Sandra Sattolo)가 발표한 변형으로, 무작위 인덱스 j를 0 ≤ j ≤ i-1 범위에서 선택한다. 이는 길이 n의 단일 사이클로 구성된 순환 순열만을 생성한다.

인사이드-아웃(Inside-out) 알고리즘

배열의 초기화와 셔플을 동시에 수행하는 변형으로, 별도의 초기화 없이 소스 데이터를 순차적으로 처리하면서 무작위 위치에 삽입한다. 소스 데이터의 길이를 미리 알 필요가 없다는 장점이 있다.

병렬 셔플

1990년 앤더슨(Anderson)이 공유 메모리 환경을 위한 병렬 버전을 개발하였고, 2015년에는 MERGESHUFFLE 등 추가적인 병렬 알고리즘이 제안되었다.

응용 분야

카드 게임에서의 덱 셔플링
통계 시뮬레이션 및 부트스트래핑
무작위 샘플링
게임에서 아이템 드롭 순서 결정
머신러닝 데이터 셔플링
몬테카를로 방법(Monte Carlo method) 등 무작위 알고리즘
테스트 데이터 무작위화

참고 문헌

Fisher, R. A., & Yates, F. (1938). Statistical Tables for Biological, Agricultural and Medical Research. Oliver & Boyd.
Durstenfeld, R. (1964). "Algorithm 235: Random permutation". Communications of the ACM, 7(7), 420.
Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.

역사