C#

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

주어진 Rand5() 하나를 이용해서는 6,7에 대한 숫자를 구할 수 없으므로, 두개를 이용하여 풀 수 있는지 검토한다. 두 개의 Rand5() 결과를 직접 더하는 것만으로는 2부터 10까지를 구할 수 있지만, 균등한 확률로 랜덤 숫자를 산출할 수 없다. 균등한 확률로 숫자를 선발하기 위해서 첫번째 Rand5()는 1부터 5를 리턴하고, 두번째 Rand5()로부터는 리턴값에서 1을 빼고(첫번째값 1~5만이 유효하도록) 다시 5배를 곱해서 5~10, 11~15, 16~20, 20~25까지의 숫자를 생성한다. 이렇게 되면, 1부터 25까지의 숫자는 균등한 확률로 나오게 된다.

int Rand7()
{
    while (true)
    {
        int r = 5 * (Rand5() - 1) + Rand5();
        if (r <= 21)
        {
            return r % 7 + 1;
        }
    }
}

문제는 1~7까지만 리턴해야 하므로 1부터 21까지의 숫자만 유효하다고 보고, 22,23,24,25에 대해서는 무시한다 (Rejection Sampling). 22 이상의 경우는 다시 랜텀 넘버를 가져오도록 계속 Loop를 돈다 (계속적으로 22이상만 나온다면 무한 루프에 빠지겠지만, 이런 확률은 거의 없다고 본다)