C++에서 rand7()만 사용해 rand10() 구현하는 방법

rand7() 함수가 1부터 7 사이의 균등한(uniform) 무작위 정수를 반환한다고 가정해 봅시다. 이때 별도의 난수 생성 라이브러리 함수를 사용하지 않고, 1부터 10 사이의 균등한 무작위 정수를 반환하는 rand10() 함수를 구현하는 것이 목표입니다.

접근 방법: 기각 샘플링(Rejection Sampling)

핵심 아이디어는 기각 샘플링입니다. rand7()을 두 번 호출하면 각 호출마다 7가지 결과가 나올 수 있으므로, 총 7 × 7 = 49개의 동일한 확률을 가진 조합을 만들 수 있습니다. 이 조합들을 다음 식으로 하나의 정수로 변환합니다.

(rand7() - 1) * 7 + (rand7() - 1)

이 식은 0부터 48까지의 값을 균등한 확률로 생성합니다. 여기서 40 이상인 값은 버리고 다시 생성합니다(기각 단계). 남은 0부터 39까지의 값은 정확히 40개이며, 40은 10으로 나누어떨어지므로 각 숫자(1~10)가 정확히 같은 개수(4개씩)의 원본 값에 대응됩니다. 따라서 % 10 + 1 연산을 적용하면 1부터 10까지 완벽하게 균등한 분포를 얻을 수 있습니다.

알고리즘 단계

• rand40 := 40으로 초기화합니다.
• rand40 >= 40인 동안 반복합니다.
  • rand40 := (rand7() - 1) * 7 + (rand7() - 1)
• rand40 % 10 + 1을 반환합니다.

기대 실행 횟수 측면에서도 효율적입니다. 매 시도마다 약 40/49(약 81.6%)의 확률로 성공하므로, 평균적으로 rand7()을 약 2.45번 호출하면 됩니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

int rand7(){
    return 1 + rand() % 7;
}

class Solution {
    public:
    int rand10() {
        int rand40 = 40;
        while(rand40 >= 40){
            rand40 = (rand7() - 1) * 7 + (rand7() - 1);
        }
        return rand40 % 10 + 1;
    }
};

main(){
    srand(time(NULL));
    Solution ob;
    cout << (ob.rand10()) << endl;
    cout << (ob.rand10()) << endl;
    cout << (ob.rand10()) << endl;
}

입력

함수를 세 번 호출

출력

2
2
6

정리

이 방법의 장점은 두 가지입니다. 첫째, rand7()이라는 주어진 난수원만 활용하므로 추가 라이브러리가 필요 없습니다. 둘째, 40 이상의 값을 기각함으로써 편향(bias) 없이 완전히 균등한 분포를 보장합니다. 만약 49개 값을 모두 사용하고 9개만 기각하는 대신 다른 범위를 활용하고 싶다면, 기각되는 값의 비율을 줄여 효율을 더 높이는 변형 기법도 고려할 수 있습니다.