C++에서 std::vector 요소를 무작위로 섞는 방법 (Fisher-Yates 셔플)

C++에서 std::vector의 요소를 무작위로 섞으려면 Fisher-Yates 셔플 알고리즘을 사용할 수 있습니다.

이 알고리즘은 벡터를 선형으로 한 번 훑으면서, 각 요소를 자기 자신을 포함한 나머지 요소들 중에서 무작위로 선택한 요소와 서로 맞바꾸는(swap) 방식으로 동작합니다. 이 방식은 모든 순열이 동일한 확률로 나타나도록 보장하며, 시간 복잡도는 O(n)으로 매우 효율적입니다.

알고리즘

시작
  show() 함수를 선언한다.
      show() 함수에 벡터의 const 참조를 매개변수로 전달한다.
      for (auto const& i : input)
          변수 i의 값을 출력한다.
    벡터 타입의 v를 선언한다.
        배열 형태로 v 벡터에 초기값들을 넣는다.
    정수형 변수 size를 선언한다.
        size() 함수를 호출해 벡터의 크기를 구하고 size = v.size()로 초기화한다.
    for (int i = 0; i < size - 1; i++)
        int j = i + rand() % (size - i);
        swap() 함수를 호출해 v[i]와 v[j]의 값을 맞바꾼다.
    "셔플 후의 요소들"이라는 문구를 출력한다.
    show() 함수를 호출해 섞인 v 벡터의 값을 화면에 표시한다.
끝.

예제 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void show(vector<int> const &input) {
   for (auto const& i: input) {
      std::cout << i << " ";
   }
}

int main() {
   vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
   int size = v.size();

   for (int i = 0; i < size - 1; i++) {
      int j = i + rand() % (size - i);
      swap(v[i], v[j]);
   }

   cout << "Elements after getting shuffled" << endl;
   show(v);

   return 0;
}

실행 결과

Elements after getting shuffled
2 8 5 3 1 9 4 7 6

참고 사항

위 예제에서는 난수 생성을 위해 rand() 함수를 사용했습니다. 다만 rand()는 난수의 품질이 떨어지고 범위 제한이 있기 때문에, 실무 환경에서는 C++11부터 도입된 <random> 헤더의 std::mt19937과 std::uniform_int_distribution을 함께 사용하는 것이 권장됩니다. 또한 표준 라이브러리에서 제공하는 std::shuffle(v.begin(), v.end(), rng) 함수를 사용하면 위 과정을 직접 구현하지 않고도 간편하게 안전한 셔플을 수행할 수 있습니다.