LeetCode - 고유한 이진 검색 트리

문제 설명

정수 n이 주어지면 구조적으로 고유한 **BST's*(이진 검색 트리)의 수를 반환합니다. 이 수는 1에서 n*까지 고유한 값의 정확히 n개의 노드를 가집니다.

다음에서 가져온 문제 설명: https://leetcode.com/problems/unique-binary-search-trees .

예 1:

Input: n = 3
Output: 5

예 2:

Input: n = 1
Output: 1

제약:

- 1 <= n <= 19

설명

무차별 대입 솔루션

무차별 대입 방식은 가능한 모든 BST를 생성하고 카운트를 얻는 것입니다. 이 접근법은 우리가 n을 증가시킬 때 많은 시간을 소비할 것입니다.

동적 프로그래밍

동적 프로그래밍을 사용하면 BST 생성 범위를 줄이고 수학적 개념을 사용하여 필요한 결과를 얻을 수 있습니다.

n이 5인 경우를 예로 들어 보겠습니다. 노드 2가 루트이면 왼쪽 하위 트리에는 1이 포함되고 오른쪽 하위 트리에는 3, 4 및 5가 포함됩니다. 왼쪽 하위 트리에서 가능한 조합 수는 1이고 오른쪽 하위 트리는 5입니다. 1과 5를 곱합니다. 마찬가지로 루트 노드가 3이면 왼쪽 하위 트리의 가능한 조합 수는 2이고 오른쪽 하위 트리의 조합 수는 2입니다. 따라서 총 루트 노드가 3일 때 BST는 2*2 = 4입니다. 각 노드 1에서 n까지 이러한 모든 조합을 더하고 필요한 결과를 반환합니다.

위 접근 방식의 C++ 스니펫은 다음과 같습니다.

int numberOfBST(int n) {
    int dp[n + 1];
    fill_n(dp, n + 1, 0);

    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = dp[i] + (dp[i - j] * dp[j - 1]);
        }
    }

    return dp[n];
}

위 접근법의 시간 복잡도는 O(N^2)이고 공간 복잡도는 O(N)입니다.

카탈루냐 숫자

[카탈로니아 숫자(https://en.wikipedia.org/wiki/Catalan_number)는 조합 수학에서 다양한 계산 문제에서 발생하는 일련의 자연수이며 종종 재귀적으로 정의된 객체를 포함합니다.

Cn으로 표시되며 계산 공식은 다음과 같습니다.
(2n)!/((n + 1)! * n!).

이 공식을 어떻게 사용할 수 있는지 알아보기 위해 알고리즘을 확인해 봅시다.

// numTrees function
- return catalan(2*n, n)

// catalan function
catalan(n , k)
- set result = 1

- if k > n - k
  - k = n - k

- for i = 0; i < k; i++
  - result *= (n - i)
  - result /= (i + 1)

- return result/(k + 1)

이 접근법의 시간 복잡도는 O(N)이고 공간 복잡도는 O(1)입니다. C++, Golang 및 Javascript의 솔루션을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    long long catalan(int n, int k) {
        long long result = 1;

        if(k > n - k) {
            k = n - k;
        }

        for(int i = 0; i < k; i++) {
            result *= (n - i);
            result /= (i + 1);
        }

        return result/(k + 1);
    }

    int numTrees(int n) {
        long long result = catalan(2*n , n );

        return (int) result ;

    }
};

골랑 솔루션

func catalan(n, k int) int {
    result := 1

    if k > n - k {
        k = n - k
    }

    for i := 0; i < k; i++ {
        result *= (n - i)
        result /= (i + 1)
    }

    return result/(k + 1)
}

func numTrees(n int) int {
    return catalan(2*n , n )
}

자바스크립트 솔루션

var catalan = function(n, k) {
    let result = 1;

    if(k > n - k) {
        k = n - k;
    }

    for(let i = 0; i < k; i++) {
        result *= (n - i);
        result /= (i + 1);
    }

    return result/(k + 1);
}

var numTrees = function(n) {
    return catalan(2*n, n);
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

Input n = 4

Step 1: result = catalan(2*n , n )
               = catalan(2*4, 4)
               = catalan(8, 4)

// catalan function
Step 2: result = 1
        n = 8, k = 4

Step 3: if k > n - k
           4 > 8 - 4
           4 > 4
           false

Step 4: loop for i = 0; i < k
          0 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 1 * (8 - 0)
                  = 8

          result /= (i + 1)
                  = result / (i + 1)
                  = 8 / (0 + 1)
                  = 8

          i++
          i = 1

Step 5: loop for i < k
          1 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 8 * (8 - 1)
                  = 8 * 7
                  = 56

          result /= (i + 1)
                  = result / (i + 1)
                  = 56 / (1 + 1)
                  = 56 / 2
                  = 28

          i++
          i = 2

Step 6: loop for i < k
          2 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 28 * (8 - 2)
                  = 28 * 6
                  = 168

          result /= (i + 1)
                  = result / (i + 1)
                  = 168 / (2 + 1)
                  = 168 / 3
                  = 56

          i++
          i = 3

Step 7: loop for i < k
          3 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 56 * (8 - 3)
                  = 56 * 5
                  = 280

          result /= (i + 1)
                  = result / (i + 1)
                  = 280 / (3 + 1)
                  = 280 / 4
                  = 70

          i++
          i = 4

Step 8: loop for i < k
          4 < 4
          false

Step 9: return result/(k + 1)
               70/(4 + 1)
               70/5
               14

So we return the answer as 14.