분수 이진탐색과 Stern–Brocot tree

0. 서론

실수 자료형을 사용하는 이진탐색은 오차때문에 틀릴 수 있습니다. 또한, 정확한 분수를 구해야 하는 문제의 경우는 실수 자료형을 쓸 수도 없습니다. 이런 경우 사용할 수 있는 방법으로는, 실수 대신 분수로 이진탐색을 하는 것입니다. (단, 분모의 상한이 확실하게 존재해야 합니다. 분모나 분자의 상한을 모른다면 답을 구할 수 없겠죠.) 증명은 정수론 학부과정에 포함되지만, 여기서는 다루지 않고 직관적으로 가능하다는 것으로 넘어가겠습니다.

실무에서는 딱히 중요하지 않을 것 같고, PS로도 자주 나오는 테크닉은 아닙니다. 그리고 코드도 실수 이진탐색보다 훨씬 더 길고 복잡합니다. 하지만 분수로 이진탐색이 된다는 것은 꽤 좋은 도구라고 생각하기 때문에 배우면 언젠가는 도움이 될 것 같습니다. 그리고, 이해를 못해도 팀노트 복붙으로 문제를 해결할 수도 있습니다.

Stern–Brocot tree 영문위키

1. Stern–Brocot tree

 

Stern-Brocot tree는 모든 분수를 무한 이진 트리 형태로 구성한 것입니다. 특징은,

1) 노드의 깊이가 깊을수록 분모의 값이 커집니다.

2) 중위순회를 했을 때 정렬된 형태입니다. (이진 탐색 트리와 비슷하게 됩니다)

위키에서는 위의 그림처럼 표현하지만, 각 노드는 구간으로 구성하는 것이 이해하기 편합니다.

트리를 만드는 방법은 다음과 같습니다. 

1) 루트는 [0/1, 1/0] 으로 정합니다. 

2) 노드 [a/b, c/d] 를 쪼갤 때, 왼쪽 노드는 [a/b, (a+c)/(b+d)], 오른쪽 노드는 [(a+c)/(b+d), c/d] 으로 구성합니다.

증명은, 아쉽게도 까먹었습니다. (그리고 알고있다고 해도 적기에는 너무 깁니다)

2. 이진탐색하기

편의상 x라는 값을 찾는다고 합시다.

개념적으로는 "위의 트리를 이진탐색트리라고 생각하고, 그 트리에서 이진탐색을 한다." 라고 생각하면 됩니다. 깊이가 깊어질수록 분모가 커지기 때문에, 왼쪽 구간에 포함되면 왼쪽으로, 아니라면 오른쪽으로 따라 내려가다가 분모가 일정 크기 이상이 되면 탐색을 멈추면 됩니다.

라고 처음에 생각했지만, 생각보다 난관이 있었습니다. 놀랍게도 단순하게 구현하면 시간복잡도가 선형입니다. 루트에서 왼쪽으로만 탐색하면 분모가 1씩 늘어나기 때문에, 이진탐색트리를 단순히 탐색하면 선형이 됩니다.

해결방법은 한 번에 많이 내려가는 겁니다. 노드 [a/b, c/d] 에서 다음 노드를 탐색할 때, 왼쪽으로 (혹은 오른쪽으로) 몇 번이나 가게 될 지 이진탐색으로 찾아야 합니다. 

즉, 다음 분수 리스트에서 이진탐색을 하여 x가 포함된 구간을 찾아야 합니다.

이 리스트에서 적절한 구간을 찾는다면, 다음 노드는 분모가 2배 이상 늘어나기 때문에 로그 시간복잡도가 보장됩니다.

(리스트에 있는 모든 구간에 대해, 시작과 끝 모두 분모는 b+d보다 크거나 같다는 것을 확인하세요. 기존 방식은 한쪽의 분모만 증가했기 때문에 로그 시간복잡도가 보장되지 않은 것입니다.)

3. 구현 (TBD)

무한한 분수 리스트에서 탐색을 진행해야 하기 때문에 구현이 엄청나게 귀찮습니다. 때문에 효율적인 구현 방법을 고민중입니다.