Rand(0,1)로 Rand(a,b) 구하기

요즘은 Rand() 함수의 파라미터로 a, b 를 넣으면 a ~ b 의 난수가 얻어진다.

Rand (0, 1)은 2가지 bit(0, 1)을 return 한다는 가정이다.

이 경우, Rand (a, b)를 구하는 방법을 생각해봤다.

a와 b가 정수(자연수)라 생각하면 a, b 모두 2진수로 표현할 수 있다.

ex) a = 4 , a = 100

b = 9 , b = 1001

Rand 2는 bit를 return하니.. 간단하게 bit의 개수로 a, b 를 구할 수 있다 생각했다.

우선, 최대 bit로 이루어진 tree를 구성한다.

ln (A ? B)의 높이를 가진 Tree가 생성이 된다.

위 예로 그린다면

H

├───────┐

0                1

├──┐         ├──┐

0       1         0      1 

┣─┐ ┣─┐   ┣─┐  ┣─┐

0    1   0   1    0    1   0   1   

┣┓┣┓┣┓┣┓┣┓┣┓┣┓┣┓

0  1 0 1 0 1 0  1 0 1 0 1 0  1 0 1

빨간 0100(2)가 최소 값 a

파란 1001(2)가 최대 값 b

left bound 와 right bound의 경우 inner bound로 들어간다.

ex) 0 -> 0 의 경우 leaf가 존재하지 않으므로 1로 들어간다.

1 -> 1 의 경우 leaf가 존재하지 않으므로 0로 들어간다.

Space : O( n ) == Tree생성

Time : O( ln( n ) ) == n의 bit수