[Javascript] Fisher-Yates 알고리즘으로 랜덤 값 가져오기

Fisher-Yates 알고리즘으로 랜덤 값 가져오기

Fisher-Yates 알고리즘은 '완전히 균등한 확률의 무작위 순열'을 보장하는 알고리즘입니다.

자바스크립트에서 무작위 값을 추출할 수 있는 Math.random() 함수와 어떤 차이가 있는지

쉽게 알아보겠습니다.

차이점

먼저 두 알고리즘은 사용의 목적이 조금 다릅니다.

 

Fisher-Yates 알고리즘은 무작위 순열을 생성하기 위해 사용되며 Math.random() 함수는 임의 값을 생성합니다.

즉, n개의 요소를 가진 배열을 무작위로 섞고 싶은지, 아니면 무작위 인덱스 한 개를 뽑아내고 싶은지에 따라 다릅니다.

Fisher–Yates 알고리즘의 구조

Fisher-Yates 알고리즘은 배열을 순회하면서 뒤에서부터 하나씩,

아직 섞이지 않은 영역에서 무작위로 하나를 골라 위치를 교환하는 방식으로 배열을 정렬합니다.

function fisherYatesShuffle(array) {
  const arr = [...array]; // 원본 보호를 위한 배열 복제
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

const list = [1, 2, 3, 4, 5];
const shuffled = fisherYatesShuffle(list);
console.log(shuffled);

“랜덤 값 하나만” 뽑고 싶다면?

그럴 땐 Fisher-Yates 알고리즘과 Math.random() 함수 중 하나를 골라 사용하면 됩니다.

✔ Fisher–Yates 활용 방식

배열 전체를 무작위로 섞은 다음 첫 번째 인덱스의 값을 가져옵니다.

function pickRandomOne(array) {
  const shuffled = fisherYatesShuffle(array);
  return shuffled[0];
}

✔ Math 활용 방식

랜덤으로 인덱스 하나를 추출한 뒤 배열에서 값을 가져옵니다.

function pickRandomOneSimple(array) {
  return array[Math.floor(Math.random() * array.length)];
}

Fisher–Yates 알고리즘의 특징

솔직히 개발을 할 때 장단점을 모두 따지고 알고리즘을 활용하지는 않지만,

그래도 분량을 좀 채우기 위해 알아보도록 하겠습니다.

✅ 장점

1. 완전한 균등성 보장
2. 성능이 꽤괜
3. 구현이 매우 단순 & 쉬운 알고리즘

❌ 단점

1. 난수의 품질은 여전히 Math.random()에 의존하기 때문에 암호학적으로 안전하지는 않음
2. 배열 전체가 필요하기 때문에 단일 값 사용엔 비효율적

언제 Fisher–Yates를 써는 것이 좋을까?

이 알고리즘은 랜덤한 것처럼 보이는 것이 아니라 진짜로 공정한 무작위 수열이 필요할 때 사용하면 좋습니다.

주로 보안과 관련 없는 부분에서 사용하는 것이 좋고 UI 구성에 특히 활용도가 높습니다.

✅ 권장

• 추첨 / 랜덤 순서 배치
• 카드 셔플
• 랜덤 퀴즈 문제 순서
• 균등한 랜덤배치를 보장해야 하는 UI나 로직

❌ 비권장

• 단순한 랜덤 인덱스 추출
• 보안 토큰 / 인증 토큰
• 매우 큰 배열에서의 단일 값

마치며

이 글을 읽으시는 분들께서는 저처럼 이상한 알고리즘으로 랜덤배열 구현했다가 새로고침 해도 연속 세 번 같은 첫 화면이 나오는 불상사를 겪지 않으셨으면 합니다.

 

감사합니다!