ho94949's profile image

ho94949

February 9, 2019 15:00

랜덤 올바르게 사용하기

random

서론

프로그램을 작성할 때 랜덤한 요소는 많이 들어갑니다. 어떤 공간을 탐색할 때 무작위로 탐색을 하기도 하고, 프로그램의 비밀 키를 만들거나 게임을 만들 때 카드 덱을 섞을 때 등, 랜덤이 프로그램에 사용되는 곳은 굉장히 많습니다. 하지만 이 랜덤은 자주 잘못 사용되고는 합니다. 랜덤을 올바르게 사용하는 방법에 대해 알아보려고 합니다.

랜덤이란?

랜덤이란 특정한 패턴이 없다는 것을 말합니다. 즉, 어떤 규칙에 의해 생성되지 않고 다른 변수와 독립적으로 만들어진 결과를 랜덤한 결과라고 합니다.

과연 완벽한 좋은 랜덤을 만들 수 있을까요? 좋은 랜덤이라는것은 어떤 랜덤을 의미할까요? 좋은 랜덤은 예측하기 힘든 랜덤을 의미합니다. 좋은 랜덤을 테스트 하기위한 검사들이 많이 존재하고, 특정한 실험에 대해 파편화된 경향을 나타내거나, 다음 숫자를 예측하기 쉬우면 좋은 랜덤이라고 하기 힘듭니다. 또한 담고 있는 정보량이 많을 수록 (간단히 말해서, 0과 1을 만든다고 하면 0이 나올 확률이 0.5에 가까울수록) 좋은 랜덤입니다.

이 랜덤성을 만드는것은 생각보다 어렵습니다. 예를 들면 사람은 좋은 랜덤을 만들지 못합니다. 이 페이지는 기계가 사람의 랜덤성을 얼마나 잘 예측 할 수 있는지 보여주며, 사람의 랜덤에 대해 70%의 정확성을 보입니다. 가령이면, 대부분의 사람에게 랜덤하게 동전 앞뒷면을 던진 결과 20개를 말하라고 하면, 연속된 5개가 같은 경우가 거의 없을 것입니다. 하지만, 앞뒷면이 동등하게 나오는 동전에 대해서는, 실제로 연속된 같은 수 5개가 존재할 확률은 43%입니다. 연속된 6개가 같은 수일 확률은 22%이고, 7개일 확률은 11%입니다. 사람들은 이런 경우를 간과하는 경향이 있습니다.

그래서 랜덤을 만드는 좋은 방법은 어떤것들이 있을까요? 하나는 실제로 다른 수와 거의 연관이 없는 물리적인 수치를 사용하는 것입니다. 랜덤을 제공하는 random.org는 자연에서의 대기 노이즈를 이용하여 랜덤을 제공합니다. 좀 더 올바른 랜덤은 양자역학을 이용하는 방법이 있습니다. 이론적으로 예측될 수가 없기 때문에 거의 올바른 랜덤이라고 받아들여지고 있습니다. 붕괴하는 방사성 물질을 두고 가이거 카운터 등으로 측정하는 등 다양한 방법을 사용합니다.

유사 난수 생성기 (Pseudo-Random Number Generator)

우리는 자연계에서 방대한 양의 랜덤 소스를 얻기 힘들기 때문에, 보안과 관련된 true random이 필요한 곳이 아니면, 자연계에서 적당한 양의 랜덤 소스를 얻고 유사 난수 생성기를 사용합니다. 유사 난수 생성기는 적당한 양의 시작값(seed)를 기반으로 랜덤이라고 고려될 수 있는 수열을 만듭니다.

C의 rand()함수는 대부분의 경우 Linear Congruential Generator를 이용합니다. (Java에서의 Random())수열에서 $X_0$ 의 값을 주어진 seed로 설정하면, 다음과 같은 함수를 이용해서 다음 수를 만듭니다: $X_{n+1} = (aX_{n}+c) \bmod m$

RNG의 상태는 $m$ 가지 중 하나를 가지고, 좋은 $a$ 와 $c$를 설정하지 않으면 $m$가지 보다 더 적은 수를 가지게 될 수도 있습니다. ($a$와 $c$를 신중하게 생성하지 않는다면, Birthday’s Paradox 에 의해 $1.2\sqrt{m}$ 개 정도의 상태를 가질 것 입니다.)

상태가 $m$가지가 되게 하는 $a$와 $c$를 설정하는 방법은 다음과 같습니다(Hull-Dobell 정리):

  1. $m$과 $c$는 서로소여야 한다.
  2. $a-1$은 $m$의 소인수 모두로 나누어 떨어져야한다.
  3. $m$이 4로 나누어 떨어져야 한다면 $a-1$도 4로 나누어 떨어져야 한다.

머신에서의 구현 편의 상 $a$는 $4k+1$ 꼴, $m$은 $2^w$ 꼴로 정해지게 됩니다. 그리고 특정한 상위 비트를 반환하게 됩니다. (모든 비트를 반환 하면, 같은 수는 $m$번 동안 절대 나오지 않을 것이고, 주어진 수는 홀수와 짝수를 번갈아가면서 나오게 될 것 입니다.)

이 LCG는 구현이 쉽고 저장해야하는 상태의 수가 적지만, $a$ 와 $c$를 신중하게 설정한다고 하더라도 문제가 있고, 연산이 어느정도 비싸기 때문에 이런 문제들을 해결하기 위해 Mersenne-Twister 알고리즘이 1997년에 나오게 됩니다. 이는 저장하는 상태의 수가 크고(일반적인 구현에서는 2.5KB), xor과 쉬프트 연산을 사용하기 때문에 CPU에서 싼 값으로 구현 될 수 있습니다. (임베디드 장치 등에 들어가기에는 메모리가 문제가 될 수도 있습니다.)

C++에서는 C++11부터 random 헤더에 정의된 mt19937 혹은 mt19937_64 로 이용할 수 있고, Python은 내장되어 있는 Random함수가 있고, Java는 외부 구현체를 써야합니다.

랜덤을 고르고 가공하기

1비트 만들기

대부분의 자연계의 랜덤 소스는 0과 1이 나올 가능성이 같지 않습니다. 하지만 각 확률은 독립적입니다. 일단 0과 1이 나올 확률을 같게 만들어 봅시다.

어떤 소스(밑의 코드에서의 true_random)에서 0이 나올 확률이 p라고 하면, 1이 나올 확률은 (1-p)입니다. 임의의 두 비트를 차례대로 봤을 때, 01이 나올 확률과 10이 나올 확률은 p(1-p) = (1-p)p으로 같기때문에, 우리는 다음의 코드로 0과 1이 나올 확률이 같은 랜덤 소스를 만들 수 있습니다. (유사코드고, 대개 Python의 문법을 따릅니다)

def random_01():
  x = y = -1
  while x == y:
  	x = true_random()
  	y = true_random()
  return x

이 random_01을 이용하면 우리는 0과 1이 같은 확률로 나오는 랜덤 변수를 만들 수 있습니다.

정수 만들기

우리는 이제 정수를 만들어야 합니다. $2^k$ 꼴의 정수를 만드는 방법은 간단하게 k 개의 비트를 이어 붙이면 됩니다. k=31 등을 사용해 일반적인 범위의 정수를 만들었다고 하고 rand() 라고 합시다. 그리고 이 함수에서 나올 수 있는 가장 큰 수를 RAND_MAX 라고 합시다. 0 이상 n 미만의 정수를 같은 확률로 만들기 위해서는 좀 더 까다로운 구현이 필요합니다. 보통 C에서 rand()%n 같이 사용하게 되는데, rand() 의 범위가 n의 배수가 아닐 경우에는 0이 나올 확률이 n-1이 나올 확률보다 커지게 되므로 반환 값을 n의 배수로 만들어 줘야 합니다.

def randInt(n):
  assert 0 < n <= RAND_MAX
  x = RAND_MAX+1
  thres = floor((RAND_MAX)/n)*n
  while x > thres:
    x = rand()
  return x%n

C++의 std::uniform_int_distribution 같은 함수가 이런 일을 해 줄 수 있습니다.

배열 섞기

이제 배열을 섞어 봅시다. 길이가 n 인 배열을 섞기 위해서는 n! 가지의 순열이 모두 골고루 나올 수 있게 해야합니다.

이 중에 첫번째 원소에는 배열의 각 원소가 나올 확률이 모두 같습니다. 두번째 원소는 결정되지 않은 나머지 수 중, 각 원소가 나올 확률이 모두 같습니다.

즉 이를 코드로 구현하면

def randomShuffle(arr):
  for i in range(len(arr)):
  	swap(arr[randInt(len(arr)-i)+i], arr[i])

와 같은 방식이 됩니다. randInt는 n, n-1, …, 1 순으로 호출이 되기 때문에 우리가 요청한 랜덤의 가짓수는 n! 이고, 이들은 모두 같은 확률로 나오며, 모든 randInt의 결과에 대해 다른 배치를 반환 하기 때문에, 모든 순열을 같은 확률로 반환한다는 것을 알려줄 수 있습니다.

우리는 흔히 다른 방식으로 배열을 셔플 합니다. 가령이면, 매 원소에 대해서 매번 1이상 n 이하의 값을 골라서 배열을 섞거나, 임의의 두 원소를 골라서 배열을 섞는 행위를 n번 정도 진행합니다. 혹은 사다리타기를 하기도 합니다.(사다리 하나는 Inversion의 홀짝성을 바굼) 이 경우 모두 확률이 예측 가능하게 되고, 좋은 셔플 방식이 아닙니다. 배열이 충분히 길면, 어떤 방법으로 섞었는지 매우 높은 확률로 알 수 있습니다.

C++의 std::shuffle같은 함수가 이런 일을 해 줄 수 있습니다.

번호 붙은 트리 생성과 Prüfer sequence

트리를 만들어 봅시다. 번호가 붙은 트리는 게임에서의 맵 제작이나, 프로그램에서 탐색 순서를 정하는 등 굉장히 중요한 주제이고, 올바른 랜덤한 방식으로 생성해야 중복된 탐색을 최대한 피하면서 고른 확률을 보장해 줄 수 있습니다.

Cayley’s formula는 정점이 n개인 번호 붙은 트리의 갯수가 $n^{n-2}$ 개라는것을 보장하고, 이를 길이 n-2에 각 원소가 1 이상 n 이하인 배열과 트리를 1대1 대응시켜줌으로써 증명합니다. Prufer sequence 는 각 단계에, leaf 중에서 가장 숫자가 작은것을 제거하고 그 노드의 이웃을 배열에 추가하는 방법으로 수열을 만듭니다.

def Tree-to-Prufer(T):
  a = Array()
  for i in range(N-2):
    x = T.smallest_index_leaf()
    a.append(x.neighbor) # only one neighbor
  return a

복구는, Prufer sequence 로 각 노드의 degree를 알 수 있고, 역으로 복구해 가면서 만듭니다.

def Prufer-to-Tree(a):
  n = len(a) + 2
  T = Tree()
  degree = [1 for i in range(n)+1]
  for i in a: degree[i]++
  for i in a:
    for j in range(1, n+1):
      if degree[j] == 1:
        T.addEdge(i, j)
        degree[i]--
        degree[j]--
        break
  (u, v) = degree.positive_index_of_1() #(deg[u] = deg[v] = 1, u, v>0)
  T.addEdge(i, j)
  return T

이래서 랜덤한 Tree를 생성하는 방법은, Prufer-to-Tree([randInt(n)+1 for i in range(n-2)]) 라는 것을 알 수 있습니다. 일반적으로 랜덤한 트리를 생성할 때, i번째 단계에서 randInt(i-1) 노드에 정점을 이은 후에 간선을 연결해서 만들어 주는데, 이 방법도 역시 확률의 차이가 존재합니다. 각 트리가 만들어질 확률도 간단한 동적 계획법으로 계산할 수 있고, N=64인 경우에 만든 방법을 99% 이상의 확률로 구분할 수 있습니다.

결론

랜덤을 올바른 방식으로 생성하는 것은 굉장히 중요하니다. 랜덤의 각 요소들이 어떻게 동작하는지 알고, 랜덤을 올바르게 (정해진 확률에 맞게 등장시키는 것) 은 굉장히 중요합니다. 랜덤을 사용해야 할 경우는 더 많고, 각 경우에 랜덤을 올바르게 사용하여 프로그램이 좀 더 예측한 대로 치우친 랜덤의 영향을 받지 않게 구현하도록 합시다.