[Algorithm][LeetCode 96] Unique Binary Search Trees

고유한 이진 탐색 트리(BST)의 개수 구하기

주어진 정수 n에 대해, 1부터 n까지의 값을 가지는 고유한 노드들로 만들 수 있는 서로 다른 구조의 이진 탐색 트리(BST)의 수를 구하는 문제입니다.

문제 예시

n = 3일 때 가능한 BST는 아래 그림과 같이 총 5가지입니다.

Input: n = 3
Output: 5

접근 방식

특정 노드 수 n에 대해 만들 수 있는 BST의 수는 재귀적으로 정의할 수 있습니다.

예를 들어 n = 3인 경우:

• 루트가 1인 경우: 나머지 노드(2, 3)는 모두 오른쪽 서브트리에 위치 → numTrees(0) * numTrees(2)
• 루트가 2인 경우: 1은 왼쪽, 3은 오른쪽 → numTrees(1) * numTrees(1)
• 루트가 3인 경우: 나머지 노드(1, 2)는 모두 왼쪽 서브트리에 위치 → numTrees(2) * numTrees(0)

즉, 다음과 같은 점화식이 성립합니다:

numTrees(n) = Σ numTrees(i) * numTrees(n - i - 1)  for i = 0 to n - 1

JavaScript 코드 구현

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const numsOfTree = new Map();
    numsOfTree.set(0, 1);
    numsOfTree.set(1, 1);

    for (let i = 2; i <= n; i++) {
        let total = 0;
        for (let root = 1; root <= i; root++) {
            const left = root - 1;
            const right = i - root;
            total += numsOfTree.get(left) * numsOfTree.get(right);
        }
        numsOfTree.set(i, total);
    }

    return numsOfTree.get(n);
};

추가 개념: 조합과 카탈란 수

조합 (Combination)

순서를 고려하지 않고, n개 중 r개를 선택하는 방법의 수입니다.

C(n, r) = n! / (r! * (n - r)!)

카탈란 수란?

특정 구조적 조합 문제에서 자주 등장하는 수열입니다. 아래와 같은 일반식으로 표현됩니다:

Catalan(n) = (1 / (n + 1)) * C(2n, n)
           = (2n)! / ((n + 1)! * n!)

카탈란 수는 다음과 같은 문제에 적용됩니다:

• 올바른 괄호 문자열의 개수
• BST 구조의 개수
• 스택 수열의 개수
• Dyck Path(절대 음수로 내려가지 않는 경로)

카탈란 수 시각화 예시

카탈란 수 공식, 나무위키 참조

카탈란 수가 적용되는 구조의 조건:

- 전체 구조는 균형 잡혀야 한다 (n개씩)

- 어떤 기준점(루트, 열림괄호 등)을 중심으로 좌/우를 독립적으로 재귀 처리 가능

- 부분 구조의 조합으로 전체 구조 구성 가능

 

예) BST 트리 구성:

        o       ← 루트 1개

       / \

    (i)  (n-1-i) ← 왼쪽 i개, 오른쪽 n-1-i개 구조

 

    총 경우의 수: Σ C[i] * C[n-1-i]

 

요약

• BST의 개수는 카탈란 수를 기반으로 계산할 수 있다.
• n개의 노드를 사용할 때 BST 구조 수는 numTrees(n) = Catalan(n)이다.
• 카탈란 수는 조합을 기반으로 유도되며, 균형 잡힌 재귀 구조를 가진 문제에서 자주 등장한다.