Fisher-Yates Shuffle 알고리즘: 완전한 무작위성을 위한 가장 공정한 방법

수업에서 모둠을 나누거나 워크숍 조를 편성할 때, "어떻게 하면 정말 공평하게 할 수 있을까?" 고민해 본 적이 있을 것입니다. 종이를 뽑거나 번호표를 나누는 수작업은 시간이 오래 걸릴 뿐 아니라, 아무래도 사람의 의도가 개입되기 쉽습니다. 디지털 도구를 사용하더라도 무작위처럼 보이지만 실제로는 특정 패턴이 반복된다면 신뢰를 잃기 쉽습니다. 이 때문에 Random Group Generator와 같은 도구는 Fisher-Yates Shuffle 알고리즘을 핵심 엔진으로 채택하고 있습니다. 이 알고리즘은 모든 순열이 동일한 확률로 등장하는 완전 무작위 배열을 보장하여, 그룹 배정의 공정성을 수학적으로 뒷받침합니다.

Fisher-Yates 셔플이란?

Fisher-Yates 셔플은 주어진 목록의 원소들을 무작위로 섞어 모든 가능한 순서가 동등한 확률로 나타나도록 하는 알고리즘입니다. 원본은 영국의 통계학자 로널드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates)가 1938년에 발표했으며, 당시에는 펜과 종이로 난수표를 이용해 수작업으로 수행하는 방식이었습니다. 이후 1964년 리처드 더스텐펠드(Richard Durstenfeld)가 컴퓨터에 최적화된 O(n) 시간 복잡도의 현대적 버전으로 개량했고, 오늘날 대부분의 프로그래밍 언어와 라이브러리에서 이 더스텐펠드 변형이 표준으로 자리 잡았습니다.

핵심 아이디어는 간단합니다. "뽑을 수 있는 항목들 중 하나를 무작위로 골라 결과 목록에 넣고, 이미 뽑은 항목은 다시 고려하지 않는" 과정을 반복하는 것입니다. 이렇게 하면 한 번도 같은 항목이 중복 선택되지 않으면서도 모든 배치가 수학적으로 동등한 기회를 갖게 됩니다.

왜 공정한 셔플이 중요한가?

그룹을 나눌 때 공정함이 깨지는 순간, 학습자나 참가자의 신뢰는 급격히 떨어집니다. 예를 들어 A팀에 유독 실력자가 몰린다면 "선생님이 일부러 그런 것 아니야?"라는 불만이 나올 수 있습니다. 진정한 무작위 섞기는 이러한 의심을 원천적으로 차단합니다. Fisher-Yates Shuffle은 모든 순열의 확률이 1/n!로 동일하기 때문에, 어떤 특정 조합이 더 자주 등장하거나 특정 인물이 항상 같은 사람과 짝이 되는 현상을 방지합니다.

실제로 Random Group Generator는 방대한 사용자 수업과 워크숍에서 이 알고리즘을 신뢰 엔진으로 활용하고 있습니다. 랜덤 그룹 생성기에 접속해 명단을 입력하면, 버튼 한 번으로 Fisher-Yates 셔플이 작동해 모든 구성원에게 똑같이 공평한 기회를 부여하는 것입니다.

알고리즘의 단계별 작동 원리

현대적 Durstenfeld 버전

현대적인 컴퓨터 구현은 배열의 끝에서부터 역순으로 진행하며, 현재 위치까지의 인덱스 중 하나를 무작위로 골라 교환(swap)하는 방식입니다. 다음은 5명의 학생(A, B, C, D, E)을 예시로 한 단계별 설명입니다.

1. 배열 [A, B, C, D, E]에서 마지막 인덱스 4를 기준으로, 0~4 사이의 난수를 생성합니다. 예를 들어 난수 2가 나왔다면, 인덱스 4의 'E'와 인덱스 2의 'C'를 교환합니다. 결과: [A, B, E, D, C].
2. 이제 고정된 마지막 원소 'C'는 더 이상 건드리지 않습니다. 인덱스 3에 대해 0~3 중 난수를 생성(예: 0). 'A'와 'D'를 교환합니다. 결과: [D, B, E, A, C].
3. 인덱스 2에 대해 0~2(예: 1). 'B'와 'E' 교환 → [D, E, B, A, C].
4. 인덱스 1에 대해 0~1(예: 0). 'D'와 'E' 교환 → [E, D, B, A, C].
5. 마지막 인덱스 0은 난수 생성 없이 그대로 종료. 최종 결과: [E, D, B, A, C].

이 과정에서 각 단계마다 선택 가능한 원소의 범위가 하나씩 줄어들며, 이미 결정된 위치는 다시 방해받지 않습니다. 따라서 모든 순열이 정확히 동일한 확률로 생성됩니다.

원본 Fisher-Yates 방법과의 차이

원본 방법은 종이에 번호를 적은 뒤 난수표를 이용해 하나씩 지워가며 새 목록을 만드는 방식이었습니다. 이는 리스트 두 개가 필요하고 지우는 과정이 번거로웠지만, Durstenfeld의 개선은 한 배열 안에서 교환만으로 셔플을 끝내기 때문에 메모리 효율과 속도가 뛰어납니다. Random Group Generator는 이 현대적 방식을 JavaScript로 구현하여, 수십 명의 명단도 순식간에 셔플할 수 있습니다.

구현 예시 (의사 코드 및 JavaScript)

프로그래밍에 익숙한 분을 위해 간단한 JavaScript 구현을 소개합니다.

function fisherYatesShuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // 0부터 i까지 무작위 인덱스
    [array[i], array[j]] = [array[j], array[i]];  // ES6 구조 분해 할당으로 교환
  }
  return array;
}

이 코드는 이름 목록이나 참가자 ID를 담은 배열을 전달받아 완전 무작위 순서로 되돌려줍니다. 실제 랜덤 그룹 생성기에서는 이렇게 셔플된 배열을 원하는 그룹 크기만큼 순서대로 잘라내어 각 그룹을 구성합니다.

다른 셔플 방법과 비교: 왜 Fisher-Yates여야 할까?

단순 무작위 교환(naive swap)의 함정

초보 개발자가 흔히 시도하는 방법은 배열의 각 위치마다 전체 범위의 임의 인덱스를 골라 교환하는 것입니다.

for (let i = 0; i < array.length; i++) {
  const j = Math.floor(Math.random() * array.length);
  [array[i], array[j]] = [array[j], array[i]];
}

이 방식은 각 항목이 원래 자기 위치로 돌아올 확률이 달라 모든 순열이 고르게 나오지 않는 문제가 있습니다. 실제로 이 방법은 특정 순서가 다른 순서보다 최대 27%까지 더 자주 나타날 수 있습니다. 그룹 편성에 사용하면 겉보기엔 무작위여도 장기적으로 불공정이 누적될 위험이 있습니다.

정렬과 난수 비교의 문제

array.sort(() => Math.random() - 0.5)와 같이 정렬 함수에 난수를 넣는 방식은 코드 한 줄로 간편해 보이지만, 정렬 알고리즘이 내부적으로 원소를 여러 번 비교하기 때문에 확률 분포가 왜곡됩니다. 이 방법은 Fisher-Yates보다 약 2~3배 느리고, 특정 원소가 제자리에 남을 확률이 높아 역시 진정한 무작위로 보기 어렵습니다.

따라서 교육 현장이나 기업 워크숍처럼 공정성이 중요한 환경에서는 반드시 Fisher-Yates Shuffle을 채택해야 합니다.

Random Group Generator에서의 실제 활용

Random Group Generator는 이 알고리즘을 단순한 셔플 이상의 목적으로 통합합니다. 명단을 입력하거나 CSV 파일, Google Classroom, Zoom, Microsoft Teams에서 참가자 목록을 가져오면, 내부적으로 배열을 만든 뒤 Fisher-Yates Shuffle로 순서를 섞습니다. 이후 설정한 그룹 크기 또는 그룹 수에 따라 배열을 분할하여 각 조를 완성합니다.

• **무작위 그룹 생성기**: 전체 명단을 셔플한 뒤 순서대로 차등 분배하여 모든 그룹이 거의 동등한 크기를 갖도록 합니다.
• **랜덤 페어 생성기**: 셔플된 명단에서 앞에서부터 두 명씩 짝을 지어주며, 홀수인 경우 마지막에 3인 1조를 반환합니다.
• **랜덤 학생 선택기**: 셔플 후 첫 번째 원소 하나만 반환하거나, 연속된 선택 시 셔플된 순서대로 차례대로 보여주어 중복 없이 공정하게 학생을 지목할 수 있습니다.

이렇게 모든 도구가 동일한 Fisher-Yates 셔플 알고리즘을 기반으로 하기 때문에, 결과의 공정성은 어느 환경에서든 일관되게 유지됩니다.

알고리즘의 한계와 Random Group Generator의 보완

Fisher-Yates Shuffle 자체는 이론적으로 완벽하지만, 실질적 무작위성은 난수 생성기(RNG)의 품질에 달려 있습니다. Math.random()과 같은 의사 난수는 충분히 무작위처럼 보이나, 엄격한 통계 검증을 통과하지 못할 수 있습니다. Random Group Generator는 브라우저에서 제공하는 crypto.getRandomValues와 같은 암호학적 난수 생성기를 활용하여 더욱 예측 불가능한 셔플을 보장합니다.

또한, 한 번 생성된 그룹을 재현하거나 저장하려면 셔플 직후 상태를 보존해야 합니다. Random Group Generator는 세션 내 결과 고정, URL 공유, CSV 내보내기 기능을 제공하여 교육자가 동일한 편성 결과를 투명하게 공개하고 필요 시 다시 확인할 수 있도록 지원합니다.

FAQ

Fisher-Yates 셔플은 정말 완전히 무작위인가요?

네, 피셔-예이츠 셔플(특히 Durstenfeld 버전)은 모든 순열이 동일한 확률로 등장하도록 수학적으로 증명된 알고리즘입니다. 배열 길이가 n이면 생성 가능한 n! 개의 모든 순서가 똑같은 빈도로 나타나므로, 특정 패턴이나 편향이 존재하지 않습니다.

Random Group Generator는 이 알고리즘을 어떻게 사용하나요?

사용자가 입력한 이름 목록을 내부 배열로 만든 뒤, Fisher-Yates Shuffle을 적용해 순서를 무작위로 섞습니다. 그런 다음 원하는 그룹 크기나 그룹 수에 맞춰 배열을 앞에서부터 잘라내어 각 조를 배정합니다. 전체 과정이 서버가 아닌 브라우저에서 실행되므로 개인정보도 안전하게 처리됩니다.

다른 셔플 방법과 비교했을 때 가장 큰 장점은 무엇인가요?

가장 큰 장점은 편향이 전혀 없다는 점입니다. 단순한 난수 교환 방식이나 정렬 기반 방식은 특정 순열이 더 자주 나타나지만, Fisher-Yates는 모든 경우의 수가 완전히 동등합니다. 교육 현장에서 공정성을 유지하는 신뢰의 기반이 됩니다.

Fisher-Yates 셔플을 직접 구현할 때 주의할 점은?

반드시 순회 방향을 배열 끝에서부터 처음으로 진행해야 합니다. 각 스텝에서 난수 생성 범위를 0 ~ 현재 인덱스로 제한하지 않으면 편향이 발생합니다. 또한, Math.random() 대신 crypto.getRandomValues()를 사용하면 더 높은 품질의 무작위성을 확보할 수 있습니다.

Fisher-Yates 셔플은 언제 처음 만들어졌나요?

원형은 1938년 로널드 피셔와 프랭크 예이츠가 통계표 연구 과정에서 고안했습니다. 컴퓨터 친화적인 현대 버전은 1964년 리처드 더스텐펠드가 발표했으며, 오늘날 대부분의 프로그래밍 언어와 난수 라이브러리에서 표준적으로 채택하고 있습니다.

이제 Fisher-Yates Shuffle 알고리즘이 왜 공정한 무작위 그룹 생성을 위한 표준인지 이해하셨을 것입니다. 직접 랜덤 그룹 생성기에서 명단을 입력하고 셔플 버튼을 눌러 보세요. 모든 구성원이 동등한 기회를 가진 그룹 편성을 단 몇 초 만에 경험할 수 있습니다.