이진 탐색 트리(BST) 개수 구하는 DP

문제 정의

자연수 1부터 N까지의 노드를 사용하여 만들 수 있는 서로 다른 이진 탐색 트리(BST) 의 개수를 구하는 문제이다.

---

핵심 개념

• BST는 왼쪽 서브트리 < 루트 < 오른쪽 서브트리 조건을 만족하는 이진 트리이다.
• 노드 값 자체가 아닌 노드 개수에 따라 구조의 경우의 수가 결정된다.
• 루트를 하나 고정하면, 그보다 작은 수들은 왼쪽 서브트리, 큰 수들은 오른쪽 서브트리에만 배치될 수 있다.

---

점화식 유도

dp[n]을 노드 n개로 만들 수 있는 BST의 개수라고 하자.
루트를 1부터 n까지 하나씩 선택해보면,

• 루트를 i로 선택했을 때
  • 왼쪽 서브트리: 노드 개수 = i - 1 → 경우 수 = dp[i - 1]
  • 오른쪽 서브트리: 노드 개수 = n - i → 경우 수 = dp[n - i]

그러므로 점화식은 다음과 같다:

dp[n] = sum(dp[i - 1] * dp[n - i]) for i in 1..n

---

초기 조건

• dp[0] = 1: 빈 트리도 하나의 경우로 간주
• dp[1] = 1: 하나의 노드로 만들 수 있는 트리는 하나

---

코드 예시 (Java)

public class UniqueBST {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int nodes = 2; nodes <= n; nodes++) {
            for (int root = 1; root <= nodes; root++) {
                int left = root - 1;
                int right = nodes - root;
                dp[nodes] += dp[left] * dp[right];
            }
        }

        return dp[n];
    }
}

---

고찰

• dp[n]은 "n개의 노드로 만들 수 있는 BST 구조의 개수" 를 의미한다.
• 특정 루트를 기준으로 좌/우 서브트리의 노드 수만 고려하면 되며,
  어떤 숫자가 들어가는지는 구조상 영향을 주지 않는다.
• 이 문제는 카탈란 수(Catalan Number) 와 동일한 구조를 가진다.