[LeetCode]Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

n이 주어지면 유니크한 BST가 몇개인지를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1,1,2] # 0~n 까지의 Unique BST 개수를 저장하는 DP. 0인 경우에는 0이지만 곱셉 연산을 하므로 1로 표기.
        # dp[n] = (dp[0]*dp[n-1]) + (dp[1]*dp[n-1-1]) + ... + (dp[n-1]*dp[0])
        
        for i in range(3, n+1): # 3~n 까지 반복
            sum_ = 0
            for j in range(i):
                sum_ += dp[j] * dp[i-1-j]
            dp.append(sum_)

        return dp[n]

접근 방법

1. dp를 통해 풀이할 수 있습니다.
2. 점화식은 다음과 같습니다. dp[n] = (dp[j] * d[[i-j-1]) + (dp[j+1] * dp[i-j-2]) ... + (dp[i] * dp[j])
3. 위 점화식을 이중 루프를 통해 수행합니다.
4. 가장 마지막 dp의 요소에 유니크한 BST 갯수가 합산되어 있습니다.

해당 문제 유형은 DP 이지만 BST를 DP로 풀이할 수 있는 이유를 설명하겠습니다.

 

먼저 DP = [1,1,2]의 의미는 다음과 같습니다.

DP[0] : DP 점화식 곱셈을 위해 존재하는 것.

DP[1] : 1로 만들 수 있는 BST 경우의 수, 1개

DP[2] : 2로 만들 수 있는 BST 경우의 수, 2개

 

n = 4인 경우를 가정하면

1. 루트 노드에는 1,2,3,4의 값이 올 수 있습니다.
2. 1이 루트 노드인 경우
   1. 왼쪽 자식은 0개가 가능하고, 오른쪽 자식에는 2~4까지 3개가 가능합니다.
   2. dp[0] * dp[3] = 1 * 5 = 5개. 즉, 루트노드가 1인경우 5개의 BST가 생성이 가능.
3. 2가 루트 노드인 경우
   1. 왼쪽은 1인 1개, 오른쪽은 3~4인 2개가 가능합니다.
   2. dp[1] * dp[2] = 1 * 2 = 2개. 즉, 루트노드가 2인경우 2개의 BST가 생성이 가능.
4. 3이 루트 노드인 경우
   1. 왼쪽은 1~2인 2개, 오른쪽은 4인 1개가 가능합니다.
   2. dp[2] * dp[1] = 2 * 1 = 2개. 즉, 루트노드가 3인경우 2개의 BST가 생성이 가능.
5. 4가 루트 노드인 경우
   1. 왼쪽은 1~3인 3개, 오른쪽은 0개가 가능합니다.
   2. dp[3] * dp[0] = 5 * 1 = 5개. 즉, 루트노드가 4인경우 5개의 BST가 생성이 가능.

정리하자면, 5 + 2 + 2 + 5 = 14개의 BST를 생성할 수 있습니다. 

따라서 DP[4] = 14로 정의할 수 있습니다.

 

이 곱하는 규칙을 점화식으로 정리하면 다음과 같습니다.

DP[n] = (DP[0] * DP[n-1]) + (DP[1] * DP[n-2]) + (DP[2] * DP[n-3]) + ... + (DP[n-1] * DP[0])

 

 

이 문제의 경우 솔루션을 참고했음에도 불구하고 이해하기까지 굉장히 오래 걸렸습니다. 트리를 그려가면서 점화식을 이해할수는 있었지만 이런 유형의 문제를 접한다면 곱셈방법을 통해 점화식을 찾아내는게 쉽지 않을 것 같습니다.