무작위 짝 배정 코드를 다시 읽다: sort 셔플의 편향과 제한 조건이 만든 무한 루프

OTO는 참가자 명단을 넣으면 무작위로 짝을 만들거나 팀을 나눠 주는 도구다. "철수-영희"처럼 함께 배정하지 않을 조합을 넣을 수도 있다. 오래 잘 쓰던 기능인데, 프로젝트 소개 글을 쓰려고 코드를 다시 읽다가 마음에 걸리는 부분이 보였다. 감으로 판단하지 않기 위해 실제 코드를 그대로 옮겨 Node에서 수십만 번 돌려 봤다. 이 글은 그 결과다.

문제 1. sort로 섞으면 공평하지 않다

OTO의 셔플은 자바스크립트에서 흔히 보는 한 줄이다.

const shuffled = [...members].sort(() => Math.random() - 0.5);

비교 함수가 무작위로 양수나 음수를 돌려주니 배열이 섞일 것 같다. 실제로 섞이긴 한다. 문제는 고르게 섞이지 않는다는 것이다. 정렬 알고리즘은 비교 결과가 일관적이라는 가정(a < b이고 b < c면 a < c) 위에서 동작하는데, 매번 무작위로 답하면 그 가정이 깨진다. 결과 분포는 엔진이 쓰는 정렬 알고리즘의 구조를 그대로 반영한다.

원소 4개와 10개짜리 배열을 각각 20만 번 섞어서, 첫 번째 원소가 각 위치에 놓인 비율을 셌다. (Node v22.22.2(V8 12.4.254.21-node.39), macOS 26.6.2 arm64(Apple M5 Pro), 2026-10-23에 글의 코드를 그대로 옮겨 실행)

방법	배열 크기	첫 원소의 최종 위치 분포 (%)
sort(() => Math.random() - 0.5)	4	35.7 / 17.3 / 15.8 / 31.3
Fisher–Yates	4	25.0 / 24.9 / 25.0 / 25.1
sort(() => Math.random() - 0.5)	10	19.6 / 13.5 / 9.0 / 7.4 / 6.9 / 7.6 / 8.1 / 8.5 / 9.2 / 10.2
Fisher–Yates	10	모든 위치 9.9~10.2

공정하다면 모든 위치가 4개일 때 25%, 10개일 때 10%여야 한다. sort 셔플에서는 첫 원소가 **제자리에 남을 확률이 4개일 때 35.7%, 10개일 때 19.6%**로 기대값의 1.4~2배다. 명단의 앞쪽에 있는 사람은 앞쪽에, 뒤쪽 사람은 뒤쪽에 남는 경향이 생긴다. 짝 배정에서는 "명단에서 가까이 적힌 사람끼리 짝이 될 확률이 높다"는 뜻이 된다. 명단을 매번 같은 순서로 불러오는 OTO에서는 무시하기 어려운 치우침이다.

해결책은 잘 알려진 Fisher–Yates 셔플이다.

export function shuffle<T>(items: readonly T[]): T[] {
  const result = [...items];
  for (let i = result.length - 1; i > 0; i -= 1) {
    const j = Math.floor(Math.random() * (i + 1)); // 0 ≤ j ≤ i
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

뒤에서부터 한 칸씩, 아직 정해지지 않은 앞부분에서 하나를 골라 그 자리에 놓는다. 모든 순열이 정확히 같은 확률로 나오고, 시간도 O(n)으로 sort(O(n log n))보다 빠르다. j의 범위가 i까지 포함한다는 점이 중요하다. i - 1까지로 잘못 쓰면 또 다른 편향이 생긴다.

문제 2. 조건을 만족할 수 없으면 스택이 터진다

1:1 짝 배정은 섞은 뒤 두 명씩 묶고, 제한된 조합이 나오면 처음부터 다시 섞는다.

const createPairs = (members: string[], restrictions: string[]): [string, string][] => {
  const shuffled = [...members].sort(() => Math.random() - 0.5);
  const pairs: [string, string][] = [];
  const restrictionPairs = restrictions.map((r) => r.split("-"));
  if (shuffled.length % 2 !== 0) shuffled.push("(없음)");
  for (let i = 0; i < shuffled.length; i += 2) {
    if (restrictionPairs.some(([a, b]) =>
      (shuffled[i] === a && shuffled[i + 1] === b) || (shuffled[i] === b && shuffled[i + 1] === a))) {
      return createPairs(members, restrictions); // 제한된 쌍이면 다시 섞기
    }
    pairs.push([shuffled[i], shuffled[i + 1]]);
  }
  return pairs;
};

"다시 뽑기"는 조건이 느슨할 때 훌륭한 전략이다. 문제는 조건을 만족하는 배정이 아예 없을 때다. 참가자가 철수와 영희 둘뿐인데 "철수-영희"를 제한하면, 몇 번을 섞어도 답이 없다. 재귀는 끝나지 않고 결국 이렇게 끝난다.

RangeError: Maximum call stack size exceeded

네 명 중 한 사람이 나머지 세 명 모두와 제한된 경우도 마찬가지로 재현된다. 사용자 입장에서는 버튼을 눌렀는데 아무 일도 일어나지 않는다. 오류가 콘솔에만 찍히기 때문이다.

답이 있더라도 조건이 빡빡하면 시도 횟수가 늘어난다. 세 명(A, B, C)에 "A-B", "A-C"를 제한하면 A가 "(없음)"과 짝이 되는 경우만 정답이라, 2,000번 실험에서 섞은 횟수(첫 시도 포함)가 평균 2.63번, 최대 18번이었다(같은 환경, 글의 createPairs 재귀 코드 기준). 참가자가 철수와 영희 둘뿐이고 "철수-영희"를 제한하는 경우는 같은 코드에서 RangeError: Maximum call stack size exceeded로 끝나는 것을 확인했다. 인원과 제한이 늘면 이 횟수는 빠르게 커지고, 재귀 깊이만큼 스택이 쌓인다.

고치는 방법은 두 단계다.

const MAX_ATTEMPTS = 5000;

export function createPairs(members: string[], restrictions: [string, string][]) {
  const blocked = new Set(restrictions.flatMap(([a, b]) => [`${a}\u0000${b}`, `${b}\u0000${a}`]));
  for (let attempt = 0; attempt < MAX_ATTEMPTS; attempt += 1) {   // 재귀 대신 반복
    const order = shuffle(members);
    if (order.length % 2) order.push("(없음)");
    const pairs: [string, string][] = [];
    let ok = true;
    for (let i = 0; i < order.length; i += 2) {
      if (blocked.has(`${order[i]}\u0000${order[i + 1]}`)) { ok = false; break; }
      pairs.push([order[i], order[i + 1]]);
    }
    if (ok) return { ok: true as const, pairs };
  }
  return { ok: false as const, reason: "조건을 만족하는 짝을 찾지 못했어요. 제한 조합을 줄여 주세요." };
}

재귀를 반복문으로 바꾸면 스택 문제가 사라지고, 시도 횟수에 상한을 두면 답이 없을 때도 반드시 끝난다. 결과를 { ok, pairs } 형태로 돌려주면 화면에서 실패를 안내할 수 있다. 제한 조합 검사는 Set으로 바꿔 매번 배열 전체를 훑지 않게 했다.

문제 3. 답이 있는데도 멈추는 팀 배정

가장 심각한 것은 팀 나누기였다. 팀 배정은 섞은 명단의 맨 앞 사람을 "현재 차례인 팀"에 넣고 다음 팀으로 넘어간다. 그 팀에 제한된 사람이 있으면 그 사람을 명단 맨 뒤로 보내고 다음 사람을 시도한다.

let currentTeam = 0;
while (shuffled.length > 0) {
  const member = shuffled[0];
  const targetTeam = teams[currentTeam];
  const hasRestriction = targetTeam.some((teamMember) =>
    restrictionPairs.some(([a, b]) =>
      (member === a && teamMember === b) || (member === b && teamMember === a)));
  if (!hasRestriction) {
    targetTeam.push(member);
    shuffled.splice(0, 1);
    currentTeam = (currentTeam + 1) % teamCount;
  } else {
    shuffled.push(shuffled.shift()!); // 맨 뒤로 보내고 다음 사람 시도
  }
}

제한에 걸렸을 때 사람은 바꾸지만 팀은 바꾸지 않는다. 남은 사람이 모두 현재 팀과 충돌하면, 명단을 영원히 돌린다. 가장 흔한 경우는 마지막 한 사람이다. 마지막 사람의 차례가 된 팀에 그 사람의 제한 상대가 있으면, 그 한 명을 맨 뒤로 보내고 다시 맨 앞에서 꺼내는 일을 끝없이 반복한다. 이 경우는 예외도 나지 않고 브라우저 탭이 그대로 멈춘다.

실제 코드와 같은 방식으로 섞은 명단에 대해 각 조건을 2만 번씩 실행하고, 1만 번 이상 반복하면 "멈춤"으로 셌다(Node v22.22.2(V8 12.4.254.21-node.39), macOS 26.6.2 arm64(Apple M5 Pro), 2026-10-23에 글의 코드를 그대로 옮겨 실행).

조건	해답 존재	멈춤 비율
6명, 2팀, 제한 A-B 하나	있음	15.2%
8명, 2팀, 제한 A-B, C-D	있음	27.9%
8명, 4팀, 제한 A-B, A-C, A-D	있음	15.4%
4명, 2팀, 제한 A-C, A-D	있음 (AB / CD)	67.3%

제한 조합을 하나만 넣어도 약 일곱 번 중 한 번은 멈춘다. 모든 경우에 조건을 만족하는 팀 구성이 분명히 존재하는데도 그렇다. 탐욕적으로 앞에서부터 채우는 방식은 초반의 선택이 나중의 선택지를 막아 버리면 되돌아갈 방법이 없다.

고치는 방법은 "되돌아갈 수 있게" 만드는 것이다. 팀 수와 인원이 작은 OTO에서는 단순한 백트래킹으로 충분하다.

export function createTeams(members: string[], restrictions: [string, string][], teamCount: number) {
  const blocked = new Set(restrictions.flatMap(([a, b]) => [`${a}\u0000${b}`, `${b}\u0000${a}`]));
  const order = shuffle(members);
  const capacity = Math.ceil(order.length / teamCount);   // 팀당 최대 인원
  const teams: string[][] = Array.from({ length: teamCount }, () => []);
  let steps = 0;

  const place = (index: number): boolean => {
    if (index === order.length) return true;
    if (++steps > 100_000) return false;                   // 안전장치
    const member = order[index];
    // 인원이 적은 팀부터 시도해 균형을 맞춘다
    const candidates = teams.map((team, i) => ({ team, i }))
      .filter(({ team }) => team.length < capacity)
      .sort((a, b) => a.team.length - b.team.length || a.i - b.i);
    for (const { team } of candidates) {
      if (team.some((other) => blocked.has(`${member}\u0000${other}`))) continue;
      team.push(member);
      if (place(index + 1)) return true;
      team.pop();                                          // 막히면 되돌린다
    }
    return false;
  };

  return place(0)
    ? { ok: true as const, teams }
    : { ok: false as const, reason: "조건을 만족하는 팀 구성을 찾지 못했어요." };
}

명단을 Fisher–Yates로 섞은 뒤, 한 사람씩 들어갈 수 있는 팀(인원 여유가 있고 제한 상대가 없는 팀)에 넣어 본다. 어느 팀에도 넣을 수 없으면 직전 사람의 배정을 되돌리고 다른 팀을 시도한다. 해답이 있으면 반드시 찾고, 없으면 false로 끝난다. 재귀 깊이는 최대 참가자 수라 스택 걱정도 없다. 무작위성은 처음 섞은 순서에서 나오므로, 같은 조건으로 다시 누르면 다른 결과가 나온다. 조장·부조장 지정처럼 OTO에 있는 다른 규칙은 이 함수 앞뒤에서 처리하면 된다.

무작위 코드는 눈으로 검증할 수 없다

세 문제 모두 몇 번 눌러 보는 것으로는 발견하기 어렵다. 결과가 매번 다르니 "잘 섞이는 것처럼" 보이고, 멈춤도 일곱 번 중 한 번이라 테스트할 때 우연히 피해 갈 수 있다. 무작위 알고리즘은 많이 돌려서 분포를 보는 테스트가 필요하다.

import assert from "node:assert/strict";
import test from "node:test";

test("shuffle은 모든 위치에 고르게 놓는다", () => {
  const counts = [0, 0, 0, 0];
  const N = 40_000;
  for (let t = 0; t < N; t += 1) counts[shuffle([0, 1, 2, 3]).indexOf(0)] += 1;
  for (const c of counts) assert.ok(Math.abs(c / N - 0.25) < 0.01);
});

test("해답이 있으면 팀 배정은 항상 성공한다", () => {
  for (let t = 0; t < 2_000; t += 1) {
    const result = createTeams(["A", "B", "C", "D", "E", "F"], [["A", "B"]], 2);
    assert.equal(result.ok, true);
  }
});

test("해답이 없으면 실패를 돌려준다", () => {
  assert.equal(createPairs(["철수", "영희"], [["철수", "영희"]]).ok, false);
});

분포 테스트는 오차 범위를 넉넉히 잡아야 가끔씩 실패하는 테스트가 되지 않는다. 4만 번이면 표준오차가 약 0.2%포인트라, 1%포인트 허용 범위에서 사실상 실패하지 않는다.

정리

문제	원인	해결
셔플 편향	sort에 무작위 비교 함수	Fisher–Yates
스택 오버플로	무조건 재귀로 다시 뽑기	반복문 + 시도 횟수 상한 + 실패 결과 반환
팀 배정 무한 루프	사람만 바꾸고 팀은 고정, 되돌리기 없음	백트래킹 + 단계 수 상한
발견이 늦음	무작위 코드를 눈으로만 확인	분포·성공률을 보는 반복 테스트

적용 결과

위 수정안은 OTO에 그대로 반영했다. 배정 로직을 src/utils/matching.ts 하나로 모으고, 화면에서는 결과가 ok: false이면 이유를 안내하도록 바꿨다. 위의 테스트에 기존 코드가 멈추던 네 가지 조건을 각각 1,000번씩 돌리는 테스트, 팀 인원 차이가 1명을 넘지 않는지, 필수 조장이 각 팀 첫 자리에 있는지 확인하는 테스트를 더해 모두 8개가 통과한다. 표에서 15.2~67.3%였던 멈춤 비율은 0이 되었고, 해답이 없는 경우에는 멈추는 대신 안내 문구가 나온다.

수정된 코드를 직접 다시 확인했다(같은 환경). OTO 저장소의 npm test는 8개 테스트가 모두 통과했고(# tests 8, # pass 8, # fail 0, 76ms), 기존 코드가 멈추던 네 가지 조건에 수정된 createTeams를 2만 번씩 돌린 결과는 다음과 같다.

조건	성공	실패
6명, 2팀, 제한 A-B	20,000	0
8명, 2팀, 제한 A-B, C-D	20,000	0
8명, 4팀, 제한 A-B, A-C, A-D	20,000	0
4명, 2팀, 제한 A-C, A-D	20,000	0

가장 자주 멈추던 마지막 조건(4명, 2팀, 제한 A-C·A-D)을 화면에서 실행하면 한 번에 결과가 나온다.

"무작위로 섞는다"는 한 줄짜리 요구 안에 공정성, 종료 보장, 실패 안내라는 세 가지 요구가 숨어 있었다. 코드는 짧아도 검증은 짧지 않아야 했다.