Python으로 서로 다른 n개의 노드로 만들 수 있는 BST(이진 탐색 트리) 개수 구하기

문제 소개

하나의 숫자 n이 주어졌다고 가정해 봅시다. [1, 2, ..., n]과 같이 연속된 값들이 있을 때, 이 n개의 서로 다른 값을 노드로 사용하여 만들 수 있는 BST(이진 탐색 트리)의 총 개수를 구해야 합니다. 단, 결과값이 너무 커질 수 있으므로 10⁹+7로 나눈 나머지를 반환합니다.

예를 들어 입력이 n = 3이라면 출력은 14가 됩니다.

접근 방법

이 문제는 카탈란 수(Catalan Number) 계산과 유사한 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 작은 부분 문제의 결과를 누적해가며 더 큰 크기의 트리 경우의 수를 구하는 방식입니다. 풀이 과정은 다음과 같습니다.

• 초기 리스트 a := [0, 1]을 생성합니다.
• 모듈러 상수 m := 10^9 + 7을 설정합니다.
• 미리 계산할 최대 크기 max_n := 1000을 지정합니다.
• k를 2부터 max_n + 1까지 반복하면서, 각 k에 대해 a[i] * a[k - i](i는 1부터 k-1까지)의 합에 1을 더한 값을 모듈러 연산 후 리스트 끝에 추가합니다.
• 최종적으로 (a[n + 1] - 1) mod m을 반환합니다.

각 단계에서 이전에 계산된 값을 재활용하기 때문에, 같은 하위 문제를 반복해서 풀지 않아도 되어 효율적입니다.

예제 코드

아래 파이썬 구현을 통해 동작을 더 잘 이해할 수 있습니다.

def solve(n):
   a = [0, 1]
   m = 10**9+7
   max_n = 1000

   for k in range(2, max_n + 2):
      a.append((1 + sum(a[i] * a[k - i] for i in range(1, k))) % m)
   return ((a[n + 1] - 1) % m)

n = 3
print(solve(n))

입력

3

출력

14

마무리

이처럼 동적 계획법을 활용하면 서로 다른 n개의 노드로 구성 가능한 BST의 개수를 빠르게 계산할 수 있습니다. n이 커져도 미리 테이블을 채워 두는 방식이므로, 여러 쿼리에 대해서도 효율적으로 답을 얻을 수 있다는 점이 이 접근법의 장점입니다.