🎲 Fisher–Yates Shuffle 알고리즘이란?

Fisher–Yates Shuffle(또는 Knuth Shuffle)은
배열의 요소를 무작위로 섞는 가장 정확한 알고리즘입니다.

많은 사람들이 array.sort(() => Math.random() - 0.5)로 섞기를 시도하지만,
이 방법은 통계적으로 편향(biased) 되어 있어 균등한 확률(random uniform) 을 보장하지 못합니다.
Fisher–Yates 알고리즘은 모든 요소가 동일한 확률로 어느 위치에도 올 수 있도록 보장합니다.

🧠 알고리즘의 기본 개념

• 배열의 끝에서부터 앞으로 순회하면서,
  아직 섞이지 않은 인덱스 구간(0~i) 중 임의의 하나를 뽑습니다.
• 현재 요소(i)와 선택된 요소(j)를 서로 교환(swap) 합니다.
• 모든 요소를 한 번씩 처리하면 완벽히 섞인 배열이 완성됩니다.

⚙️ 동작 원리 (단계별 예시)

예를 들어 배열이 [1, 2, 3, 4, 5]라면 다음과 같이 작동합니다.

결과적으로 [5, 4, 2, 1, 3]이 되어 완전히 무작위로 섞입니다.
이때 모든 원소가 동일한 확률(1/n) 로 어느 위치에든 올 수 있습니다.

💻 JavaScript 구현 예제

function fisherYatesShuffle(array) {
  // 원본 배열을 훼손하지 않기 위해 복사본 생성
  const arr = [...array];

  // 배열의 끝에서부터 앞으로 반복
  for (let i = arr.length - 1; i > 0; i--) {
    // 0 ~ i 범위 내에서 랜덤 인덱스 선택
    const j = Math.floor(Math.random() * (i + 1));

    // 현재 요소(i)와 랜덤 요소(j) 교환 (swap)
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  return arr;
}

// 사용 예시
const numbers = [1, 2, 3, 4, 5];
const shuffled = fisherYatesShuffle(numbers);

console.log('원본 배열:', numbers);
console.log('셔플 결과:', shuffled);