Quiz) 0과 1을 사용하여 랜덤한 숫자를 만들 수 있을까?

Problem

Given a function random01Generator() that gives you randomly either 0 or 1, implement a function that utilizes this function and generate numbers between 0 and 6(both inclusive). All numbers should have same probabilities of occurrence.

먼저 0과 1을 생성하는 랜덤 함수가 주어집니다.

이제 우리는 위에 주어진 함수를 통하여  주어진 값 이하의 랜덤 숫자를 반환하는 함수를 만들어보면 됩니다. 주어진 문제에서는 6이라는 값이 Input으로 주어졌습니다. 하지만 우리는 6을 넘어서 INT_MAX 값까지 동작하는 함수를 만들어보려고 합니다.

 

우선 아래 예시를 통해서 어떤 느낌인지 알아보도록 하겠습니다.

 

Example

6의 INPUT 값이 들어오면 나올 수 있는 랜덤 숫자는 [ 0 - 6 ] 총 7개의 수입니다.

on multiple runs, it gives 
3
2
3
6
0

 

Approach

• 우선 일반적인 랜덤 함수는 사용할 수 없습니다.
• 우리는 문제의 0과 1을 제공하는 랜덤 함수에서 힌트를 얻을 수 있습니다.
• 우리는 대학교에 10진수와 2진수의 변환에 대하여 배웠습니다.
• 이제 우리는 주어진 INPUT 값을 바이너리로 변환하고, 이 값보다 작은 2진수의 숫자를 만들면 됩니다.

예로 10이라는 INPUT이 주어졌다고 가정해보겠습니다.

# 10을 바이너리 변환시
1010

# 나올 수 있는 랜덤 숫자의 바이너리 리스트
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010

• 2진수에 변환에 대해 잊어버렸다면 이곳으로... https://box0830.tistory.com/155

 

이제 위의 나올 수 있는 바이너리 리스트의 값 중 하나를 만들어보도록 하겠습니다.

 

Solution (Java)

package algorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * @Reference: https://box0830.tistory.com/377
 */
public class RandomWithZeroOrOne {

    public static void main(String[] args) {
        int totalSamples = 1000000;
        int input = 10;
//        int input = Integer.MAX_VALUE;

        RandomWithZeroOrOne randomWithZeroOrOne = new RandomWithZeroOrOne();
        Map<Integer, Integer> counting = new HashMap<>();

        for (int i = 0; i < totalSamples; i++) {
            int resultValue = randomWithZeroOrOne.getRandom(input);

            if (!counting.containsKey(resultValue)) {
                counting.put(resultValue, 1);
            } else {
                counting.put(resultValue, counting.get(resultValue) + 1);
            }
        }

        for (Integer key : counting.keySet()) {
            int valueCount = counting.get(key);
            long valuePercentage = Math.round((double) valueCount * 100 / totalSamples);
            System.out.println("- Random number: " + key + ", Counting: " + valueCount + ", Percentage: " + valuePercentage + " %");
        }
    }

    private int zeroOrOne() {
        return new Random().nextInt(2);
    }

    protected int getRandom(int input) {
        String inputBinary = Integer.toBinaryString(input);
        String randBinary;
        do {
            randBinary = "";
            for (int i = 0; i < inputBinary.length(); i++) {
                randBinary += String.valueOf((zeroOrOne()));
            }
        } while (inputBinary.compareTo(randBinary) < 0);

        return Integer.valueOf(randBinary, 2);
    }
}

INPUT 값과 동일한 크기의 바이너리를 랜덤으로 만듭니다. 이후 생성한 랜덤 값이 주어진 값보다 큰 경우, 다시 만듭니다.

 

Result

- Random number: 0, Counting: 90619, Percentage: 9 %
- Random number: 1, Counting: 91385, Percentage: 9 %
- Random number: 2, Counting: 90825, Percentage: 9 %
- Random number: 3, Counting: 91080, Percentage: 9 %
- Random number: 4, Counting: 90667, Percentage: 9 %
- Random number: 5, Counting: 90848, Percentage: 9 %
- Random number: 6, Counting: 91087, Percentage: 9 %
- Random number: 7, Counting: 90569, Percentage: 9 %
- Random number: 8, Counting: 90678, Percentage: 9 %
- Random number: 9, Counting: 90792, Percentage: 9 %
- Random number: 10, Counting: 91450, Percentage: 9 %

여기서 질문이 하나 나올 수 있습니다.

 

INPUT보다 생성된 랜덤 값이 큰 경우, 첫 번째 인덱스만 '1' --> '0' 으로 변환해주면 되지 않는가? 

 

100000건의 케이스로 수정 후, 다시 한번 테스트를 진행하였습니다.

위처럼 작업을 하면 중간 값들의 결과가 많아지며 양쪽 끝 값의 값이 적어지는 분포 불균형이 발생할 수 있습니다.

인의적으로 첫 번째 인덱스를 조정함으로써 "1/2" 확률이 더 가해지기 때문입니다.

- Random number: 0, Counting: 6260, Percentage: 6 %
- Random number: 1, Counting: 6293, Percentage: 6 %
- Random number: 2, Counting: 6356, Percentage: 6 %
- Random number: 3, Counting: 12243, Percentage: 12 %
- Random number: 4, Counting: 12490, Percentage: 12 %
- Random number: 5, Counting: 12587, Percentage: 13 %
- Random number: 6, Counting: 12521, Percentage: 13 %
- Random number: 7, Counting: 12476, Percentage: 12 %
- Random number: 8, Counting: 6196, Percentage: 6 %
- Random number: 9, Counting: 6383, Percentage: 6 %
- Random number: 10, Counting: 6195, Percentage: 6 %

 

Review

처음 이 문제를 접했을 때는, 도저히 접근 방법이 떠오르지 않았습니다. 오랜만에 알고리즘 문제를 풀어봐서 그런 것 같기도 하네요.

처음에는 전혀 다른 방법으로 문제를 풀어보려고 하였습니다. 바이너리를 이용하지 않고 재귀를 돌면서 랜덤 값을 뽑아내도록요..

문제를 제대로 읽어보지 못하고 풀어보려고 해서 발생한 현상이죠. ㅜㅜ

 

그동안 너무 머리를 편하게 풀어줬던 것 같습니다. 이제 너무 감을 잃지 않게 종종 알고리즘 문제를 풀어보려고 합니다. 위처럼 풀이 과정도 남기면서요 ㅎㅎ

 

Reference

https://www.geeksforgeeks.org/implement-random-0-6-generator-using-the-given-random-0-1-generator/

Implement random-0-6-Generator using the given random-0-1-Generator - GeeksforGeeks