96. Unique Binary Search Trees

96. Unique Binary Search Trees

 

class Solution:
    def numTrees(self, n: int) -> int:
        # DP 배열 초기화 (Initialize the DP array)
        # dp[i]: i개의 노드를 사용하여 만들 수 있는 고유한 BST의 개수
        # dp[i]: Number of unique BSTs that can be formed using i nodes
        dp = [0] * (n + 1)
        dp[0] = 1  # 빈 트리의 경우, 가능한 BST는 1개 (Empty tree has one valid BST)
        dp[1] = 1  # 노드가 1개인 경우, 가능한 BST는 1개 (One node has one BST)

        # DP 계산 (Calculate DP values)
        # 2개부터 n개 노드까지 가능한 BST의 개수를 계산 (Iterate for 2 to n nodes)
        for nodes in range(2, n + 1):  # 노드 개수를 2부터 n까지 증가 (Number of nodes from 2 to n)
            for root in range(1, nodes + 1):  # 각 노드를 루트로 선택 (Choose each node as root)
                # left: 루트의 왼쪽 서브트리에 있는 노드의 개수
                # left: Number of nodes in the left subtree
                left = root - 1
                # right: 루트의 오른쪽 서브트리에 있는 노드의 개수
                # right: Number of nodes in the right subtree
                right = nodes - root
                # dp[left] * dp[right]:
                # 왼쪽 서브트리와 오른쪽 서브트리 각각의 고유한 조합의 개수를 곱함
                # Multiply the number of unique BSTs in left and right subtrees
                dp[nodes] += dp[left] * dp[right]

        # n개의 노드로 만들 수 있는 고유한 BST의 개수 반환
        # Return the number of unique BSTs that can be formed with n nodes
        return dp[n]

 

시간 및 공간 복잡도

1. 시간 복잡도:
   • O(n2): 각 n에 대해 최대 n번 루프.
2. 공간 복잡도:
   • O(n): DP 배열 사용.

---

결론

이 문제는 재귀적으로 구조를 정의하고, DP를 통해 효율적으로 계산합니다.

점화식의 개념을 이해하면 n=3과 같은 작은 예제를 손으로 계산하며 감각을 익힐 수 있습니다. 😊

 

https://youtu.be/Ox0TenN3Zpg?si=JRDSI4gGYty3Pa3O