[C++] C++ 로 중복 없는 랜덤 변수 만드는 방법 - 1

서론 (본론만 필요한 사람은 아래로)

 연합 동아리 활동을 시작한 2021년, 동아리 카페에서 한 글이 올라왔었습니다. '랜덤 변수를 중복 없이 뽑는 방법은 이거뿐인가요?'. 단순 bool 배열을 통해서 5개 정도의 수를 랜덤 하게 뽑는 내용이었습니다. 이때 당시 이 글을 보고는 '음 일단 맞는데 뭔가 부족하다'라고 생각했었고 이후에 이 문제를 계속해서 마주하기에 이를 알아보고 정리하게 되었습니다.

 

 아래 내용을 보면 아주 간단한 방식으로 하기에 그렇게 만족스러운 답은 아닌 상태입니다. 그러니 혹시나 다른 방법을 알고 계신다면 댓글로 남겨주심 감사하겠습니다.

 

 

 

일단 bool 배열로 visit 체크를 하는건 어떤 문제가 있는가?

 일단 이전에 본 bool 배열의 경우 수를 많이 뽑지 않는 경우 문제가 없습니다. 다만 이 경우 뽑을 때 중복이 나오게 됩니다. 만일 999만 9999개의 수를 중복 없이 뽑았을 때 남은 1개의 수를 고르면 1/1000만의 확률을 뚫어야 합니다. 이러면 분명 큰 시간을 잡아먹게 되겠죠. 나올지도 모르겠고요. 때문에 bool 배열로 visit 체크를 하는 건 반복할수록 좋지 않은 이야기가 됩니다.

 

 

 

로또 번호처럼 뽑으면 중복없이 나온다

 일단 여기서 제가 찾은 방법은 로또와 같은 방법입니다. 즉 수들을 전부 저장한 뒤 랜덤하게 셔플 한 후 차례로 뽑는 것입니다. C++의 기준으로는 배열을 준비한 뒤 random_shuffle, shuffle을 사용하는 것입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_LENGTH = 10000001;
vector<int> numbers;

int main(){
    numbers.resize(MAX_LENGTH);

    for(int i = 0; i < MAX_LENGTH; i++){
        numbers[i] = i;
    }

    random_shuffle(numbers.begin(), numbers.end());

    for(int i = 0; i < 5; i++){
        cout << numbers[i] << " ";
    }
}

 간단하게 구현을 한건데 일단 시드 값을 주지 않았기에 계속 같은 셔플을 진행하게 됩니다. 일단 이렇게 셔플을 하면 중복이 나오는 일은 없게 될 겁니다. 이런 식으로 원하는 수에 따라 vector크기를 조정해주면 좋을 듯합니다. 다만 살짝의 단점이 보인다면 기존의 rand()같은 방식은 아니라 공간 복잡도는 잡아먹게 되는 것입니다. 물론 1000만개 int라고 하면 40MB라 크다고 보지 않는 경우도 있겠죠. 추가적으로 random_shuffle을 하는 비용이 들기도 하죠.

 

 

 

random_shuffle / shuffle

 그러면 추가로 알아봐야 하는 게 random_shuffle과 shuffle입니다. C++ 14까지 random_shuffle을 할 수 있고 17 버전부터는 삭제되어서 더 이상 사용할 수 없게 되었습니다. 때문에 컴파일러 버전에 따른 셔플 함수를 다르게 사용해야 하는 경우가 생기게 됩니다.

 

이와 관련해서 찾아보니 shuffle_random의 경우 C에서 파생된 함수인 std::rand()을 사용하고 있습니다. shuffle의 경우 urng를 사용한다고 합니다. std::random의 경우 cppreference에서 이야기하길 퇴출 후보에 오르기도 한답니다. 또한 shuffle_random의 경우 global state를 사용하고 shuffle은 URBG라고 Uniform Random Bit Generator를 사용해 global state를 사용하지 않는다고 합니다. URBG의 경우 자세히 보지 않아서 정확하게는 모르지만 일단 global state를 사용하지 않는다는 걸 알아두면 좋을 것 같습니다.

 

 

 

참고 자료

- 랜덤 값을 찾는 아이디어를 본 곳

Get random number without repeating

 

- 왜 random_shuffle은 사라지는가?

Why are std::shuffle methods being deprecated in C++14?

 

- cppreference 에서 본 shuffle 이야기

std::random_shuffle, std::shuffle - cppreference.com