C++로 세는 고유한 이진 탐색 트리의 개수 (동적 계획법)

문제 이해하기

정수 n이 주어졌을 때, 1부터 n까지의 값을 저장하는 구조적으로 고유한(structurally unique) 이진 탐색 트리(Binary Search Tree)의 개수를 모두 구하는 문제입니다. 예를 들어 입력이 3이라면 가능한 트리 구조는 아래와 같이 총 5가지이므로 출력은 5가 됩니다.

해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있으며, 그 결과값은 수학적으로 잘 알려진 카탈란 수(Catalan Number)와 일치합니다. 핵심 아이디어는 다음과 같습니다.

i개의 노드로 만들 수 있는 고유한 BST의 개수를 dp[i]라고 정의합니다.
값 j+1을 루트로 선택하면, 왼쪽 서브트리에는 j개의 노드가, 오른쪽 서브트리에는 i-1-j개의 노드가 배치됩니다.
따라서 특정 루트에서의 경우의 수는 dp[j] × dp[i-1-j]이며, 모든 루트 후보에 대한 값을 더하면 dp[i]가 됩니다.

알고리즘 단계

크기가 n+1인 배열 dp를 생성하고 dp[0] = 1로 초기화합니다.
i를 1부터 n까지 반복합니다.
내부 반복문에서 j를 0부터 i-1까지 순회하며 dp[i] += dp[j] * dp[i-1-j]를 누적합니다.
최종 결과인 dp[n]을 반환합니다.

C++ 구현 예제

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numTrees(int n) {
      vector <int> dp(n+1);
      dp[0] = 1;
      for(int i =1;i<=n;i++){
         for(int j = 0;j<i;j++){
            //cout << j << " " << i-1-j << " " << j << endl;
            dp[i] += (dp[i-1-j] * dp[j]);
         }
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout << ob.numTrees(4);
}

입력

출력

복잡도 분석

시간 복잡도는 두 겹의 반복문 때문에 O(n²)이며, 크기 n+1의 배열 하나만 사용하므로 공간 복잡도는 O(n)입니다. 재귀적 완전 탐색보다 훨씬 효율적으로 n이 커져도 안정적인 성능을 보장합니다.