티스토리 뷰

공부

Stern-Brocot 트리

전명우 2019. 5. 21. 16:27

<그림 1> Stern-Brocot 트리

참고자료: 위키백과

 

Stern-Brocot 트리는 모든 양의 유리수가 정점과 일대일이 되는 무한한 완전 이진트리다. 또한, 이진탐색트리처럼 왼쪽에서 오른쪽 방향으로 탐색 가능하다.

연분수에 의한 트리

양의 유리수는 $q$ 는 아래와 같은 연분수 꼴로 표현할 수 있고, 이를 수열 $a$로도 표현할 수 있다.

 

$q = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_k}}}} = [a_0; a_1, a_2, \dots, a_k]$

 

여기서 $k$와 $a_0$는 음이 아닌 정수고, 나머지 $a_i$는 양의 정수다. 이러한 표현은 유일하지 않은데 다음과 같이 수열의 맨 끝 $a_k$가 $1$일 때는 중복이 있기 때문이다.

$[a_0; a_1, a_2, \dots, a_{k-1},1]=[a_0; a_1, a_2, \dots, a_{k-1}+1]$

 

이러한 성질을 이용해서 $k > 0$면서 왼쪽 형태처럼 $a_k = 1$일 경우, 오른쪽 형태처럼 $a_k \geq 2$가 되도록 변환할 수 있고 이렇게 변환할 경우 유리수 $q$를 표현하는 방법은 유일하다.

그리고 $q=1$이 아닌 경우, 유리수 $q$는 Stern-Brocot 트리에서 $[a_0; a_1, a_2, \dots, a_{k-1}+1]$이라는 부모를 가진다. 만약, $q$의 $a_k = 2$인 경우, 부모는 $[a_0; a_1, a_2, \dots, a_{k-1}+1]$이 된다.

 

예를 들어, 유리수 $\frac{23}{16}$는 $1+\frac{1}{2+\frac{1}{3+\frac{1}{2}}} = [1; 2, 3, 2]$처럼 연분수 꼴로 나타낼 수 있는데, 트리에서 부모는 $[1; 2, 3, 1] = [1; 2, 4] = 1 + \frac{1}{2 + \frac{1}{4}} = \frac{13}{9}$가 된다.

 

유리수 $q = [a_0; a_1, a_2, \dots, a_k] = [a_0; a_1, a_2, \dots, a_k-1, 1]$에게는 항상 2개의 자식이 있으며 아래와 같다.

$[a_0; a_1, a_2, \dots, a_k+1]$

$[a_0; a_1, a_2, \dots, a_k-1, 2]$

 

둘 중에 하나는 $q$보다 작은 값이고, 나머지 하나는 $q$보다 큰 값이다. 누가 더 작고 크냐는 $k$의 홀짝 여부에 따라 다르다. 만약, $k$가 홀수라면 앞에 적힌 식이 왼쪽 자식이 되고, 짝수라면 뒤에 적힌 식이 왼쪽 자식이 된다. 예를 들어, $\frac{13}{9}$의 연분수 꼴은 $[1; 2, 4]$고, 두 자식은 $[1; 2, 5] = \frac{16}{11}$ (오른쪽 자식)과 $[1; 2, 3, 2] = \frac{23}{16}$ (왼쪽 자식)이 된다.

 

모든 유리수에 대해 루트까지 가는 경로는 유일하게 나오기 때문에, 각 유리수가 정확히 한 번씩 트리에 등장함이 자명하고, 깊이 $d$에 있는 유리수는 연분수 꼴의 수열에서 각 수의 합이 $d+1$과 같다. 그리고 유리수 $q$의 왼쪽 서브트리에 있는 유리수는 모두 $q$보다 작고, 오른쪽 서브트리에 있는 유리수는 모두 $q$보다 크다.

응용문제

Stern-Brocot 트리를 PS에서 응용하는 한 가지 사례를 소개한다. 실수 $l$, $r$이 주어졌을 때, $l$보다 크면서 $r$보다 작은 유리수 $\frac{y}{x}$를 구하는데, $x$가 최소가 되어야 하고, $x$가 최소인 경우가 여러 가지인 경우 $y$도 최소인 문제가 있다고 했을 때, Stern-Brocot 트리를 이용하여 이 문제를 해결할 수 있다. (구글 코드잼 2019 R2 C)

 

이분 탐색을 통해 진행할 것인데, $s = \frac{s_a}{s_b} = \frac{0}{1}$, $e = \frac{e_a}{e_b} = \frac{1}{0}$이라고 하자. $s$, $e$의 중간점 $m = \frac{s_a+e_a}{s_b+e_b}$로 구한다. 그러면 초기 $m = \frac{0+1}{1+0} = \frac{1}{1}$이 되며, 이는 트리의 루트다. 만약 $m \geq r$이라면, $s$에 $m$을 대입하고, $m \leq l$이라면, $e$에 $m$을 대입하면 된다. 둘 다 아니라면 $l < m < r$이 만족되며, 이때, $m$의 분모는 조건 $l < v < r$를 만족하는 모든 유리수 $v$ 중에 분모가 가장 작게 되며, 동일 분모 중 분자 또한 제일 작다.

 

이를 증명하기 위해서, 첫 번째로 Stern-Brocot 트리에서 정점 $v$가 있을 때, $v$의 두 자식 $v_l$, $v_r$은 정점 $v$보다 분자 혹은 분모가 점점 커진다는 것을 알아야 한다. 이는 수학적 귀납법으로 증명 가능하며, 여기서 다루지 않는다. 두 번째로 알아야 할 것은 위에서 설명한 이분 탐색은 Stern-Brocot 트리의 루트에서 탐색을 시작하여, 점점 자식 정점으로 내려가는 꼴로 진행된다는 것이다. 즉, 이분 탐색에서 조건 $l < m < r$을 만족하는 첫 $m$은 트리에서 조건을 만족하는 정점 중 가장 깊이가 낮은 유일한 정점이라는 것이다. 두 사실 때문에, 이분 탐색으로 찾은 첫 정점은 문제에서 요구한 가장 작은 분모 → 가장 작은 분자의 조건을 만족한다.

 

마지막으로 생각해야 하는 것은 빠른 구현이다. 위의 이분 탐색을 그냥 구현한다면, 문제에서 요구한 답 $\frac{y}{x}$의 정점 깊이만큼의 시간복잡도가 걸린다. 정점 깊이는 연분수 꼴에서 수열에 있는 수의 합과 비례하므로 시간복잡도가 $O(x+y)$가 된다. Stern-Brocot 트리에서 이분탐색으로 내려갈 때, 같은 방향으로 내려가는 경우를 개선하면 전체 시간복잡도가 개선된다. 이분 탐색 도중 $m \geq r$인 경우, 트리 탐색에서 왼쪽으로 내려가야 하는데, 이후 연속으로 몇 번이나 왼쪽으로 내려갈지 또 하나의 이분 탐색으로 구할 수 있다. 즉, $\frac{ks_a+e_a}{ks_b+e_b} < r$를 만족하는 최소 $k$를 이분 탐색으로 찾아 $e$에 $\frac{ks_a+e_a}{ks_b+e_b}$를 대입함으로써 연속하여 왼쪽으로 내려가는 경우, 탐색 시간을 비약적으로 줄일 수 있다. 마찬가지로, 연속하여 오른쪽으로 내려가는 경우 또한 같은 방식으로 개선할 수 있다. 이런 식으로 탐색을 진행할 경우 시간복잡도는 $O(\lg{x+y})$가 되며, 자세한 증명은 생략한다. (증명 힌트: 탐색 경로에서 지그재그로 꺾이는 횟수는 문제에서 요구한 답을 연분수 꼴 수열로 나타냈을 때, 수열의 길이에 비례한다.)

 

 

또한, 위와 동일한 경우가 아니더라도 Stern-Brocot 트리를 이용하여 실수가 아닌 유리수 차원에서 이분 탐색을 진행할 수 있다.

'공부' 카테고리의 다른 글

Stern-Brocot 트리  (0) 2019.05.21
트리의 지름 구하기  (1) 2016.10.11
Convex Hull Optimization  (4) 2016.08.23
가장 먼 두 점 구하기  (6) 2016.07.17
Building Heap in Linear Time  (2) 2016.07.01
String Matching Algorithm  (4) 2016.06.24
댓글
댓글쓰기 폼