문제 소개
숫자 n이 하나 주어집니다. 이때 0부터 n-1까지, 즉 [0, n) 범위의 값들을 사용해 만들 수 있는 서로 다른 이진 탐색 트리(Binary Search Tree, BST)의 개수를 구하는 것이 목표입니다. 답이 지나치게 커질 수 있으므로, 최종 결과는 109+7로 나눈 나머지를 반환합니다.
예를 들어 입력이 n = 3이라면, 만들 수 있는 고유한 BST의 개수는 5가 됩니다.
핵심 아이디어: 카탈란 수(Catalan Number)
BST의 구조는 노드에 들어가는 실제 값이 아니라 노드의 개수에 의해서만 결정됩니다. 따라서 n개의 서로 다른 값으로 만들 수 있는 고유한 BST의 개수는 n번째 카탈란 수와 같습니다.
C(n) = (2n)! / ((n+1)! × n!)
팩토리얼 값은 급격히 커지기 때문에 직접 계산할 수 없습니다. 대신 모듈러 값 m = 109+7에 대해 곱셈의 나머지만을 누적하고, 나눗셈이 필요한 부분은 m이 소수라는 성질을 이용한 페르마의 소정리로 처리합니다. 즉, 분모 d에 대해 dm-2 mod m을 곱해주면 d로 나눈 것과 동일한 효과를 얻을 수 있습니다.
풀이 단계
- m := 109 + 7로 설정합니다.
- 분자 numer := 1, 분모 denom := n + 1로 초기화합니다.
- i를 1부터 n까지 반복하며 다음을 수행합니다.
- numer := numer × (n + i) 를 계산한 뒤 m으로 나눈 나머지를 저장합니다.
- denom := denom × i 를 계산한 뒤 m으로 나눈 나머지를 저장합니다.
- 반복이 끝나면 numer := numer × denomm-2 mod m 을 계산해 모듈러 역원을 적용합니다.
- numer mod m 을 반환합니다.
분모를 n+1부터 시작하는 이유는 카탈란 수 공식의 분모가 (n+1)!이기 때문입니다. 루프가 종료되면 numer에는 (n+1)×(n+2)×…×(2n)이, denom에는 (n+1)!이 누적되므로, 두 값을 나누면 정확히 C(n)이 됩니다.
Python 구현 예제
class Solution:
def solve(self, n):
m = 10 ** 9 + 7
numer = 1
denom = n + 1
for i in range(1, n + 1):
numer *= n + i
numer %= m
denom *= i
denom %= m
numer *= pow(denom, m - 2, m)
return numer % m
ob = Solution()
print(ob.solve(4))입력
4출력
14n = 4일 때 네 번째 카탈란 수인 14가 출력되는 것을 확인할 수 있습니다.
복잡도 분석
시간 복잡도는 루프의 n회 반복과 거듭제곱 연산 O(log m)을 합쳐 O(n + log m)입니다. 추가로 사용하는 변수는 상수 개뿐이므로 공간 복잡도는 O(1)입니다.