서로 다른 n개의 노드가 주어졌을 때, 이 노드들을 배치하여 만들 수 있는 이진 탐색 트리(Binary Search Tree, BST)의 개수를 구하는 문제입니다. 이진 탐색 트리의 기본 성질에 따라 왼쪽 서브트리에는 항상 루트보다 작은 값들이, 오른쪽 서브트리에는 루트보다 큰 값들이 위치하게 됩니다.
이 문제는 카탈란 수(Catalan Number)를 활용하면 효율적으로 해결할 수 있습니다. 카탈란 수 C(n)은 n개의 서로 다른 키로 구성할 수 있는 이진 탐색 트리의 개수와 정확히 일치하는 값이며, 다음 공식으로 계산됩니다.
$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$
예를 들어 입력이 n = 3이라면, 만들 수 있는 BST의 개수는 5가 됩니다.
문제 해결 접근 방법
이 문제는 조합(combination)을 계산한 뒤 카탈란 수 공식에 대입하는 방식으로 풀 수 있습니다. 단계별 과정은 다음과 같습니다.
- 조합을 계산하는 함수
ncr()를 정의합니다. 이 함수는 n과 r을 인자로 받습니다. - 결괏값
res를 1로 초기화합니다. - 만약 r이 n - r보다 크다면, r을 n - r로 바꿔 연산량을 줄입니다.
- i를 0부터 r-1까지 반복하며 다음을 수행합니다.
res = res × (n - i)res = res ÷ (i + 1)의 몫을 저장합니다.
res를 반환합니다.- 메인 로직에서는 다음을 수행합니다.
c = ncr(2n, n)을 계산합니다.c ÷ (n + 1)의 몫을 결과로 반환합니다.
참고로 카탈란 수열의 초반 값은 1, 1, 2, 5, 14, 42, ... 순으로 증가하며, n = 3일 때의 값이 바로 5입니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.
from math import factorial
def ncr(n, r):
res = 1
if r > n - r:
r = n - r
for i in range(r):
res *= (n - i)
res //= (i + 1)
return res
def solve(n):
c = ncr(2 * n, n)
return c // (n + 1)
n = 3
print(solve(n))
입력
3
출력
5
복잡도 분석
ncr() 함수는 최대 r번의 곱셈과 나눗셈을 수행하므로 시간 복잡도는 O(n)입니다. 따라서 전체 알고리즘 역시 O(n)의 시간 복잡도를 가지며, 매우 효율적으로 동작합니다.