[알고리즘]#카탈란 수열, DP

#1. 카탈란 수

 

1. 개념

키탈란 수는 조합론에서 매우 중요한 수열로 특정한 제약 조건을 가진 구조의 개수를 세는 수열. 카탈란 수열의 n번째 항인 C(n)은 균형 잡힌 괄호 구조의 개수를 나타냄. 

 

2. 응용

1. 균형 조건: 어떤 지점에서도 특정 값이 다른 값을 초과하지 않는 균형 제약이 있을 경우
2. 재귀적 구조
3. 이진 구조의 경우의 수: 주어진 노드 개수로부터 모든 가능한 이진 트리, 이진 검색 트리 등의 개수를 세는 문제

/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929
    @문제: 올바른 괄호의 갯수
    @되풀이 여부: o
    @되풀이 횟수: 0
    @설명
        1. 카탈린의 수 - n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 쌍 조합
        2. 점화식
        - dp[i] = dp[j] * dp[i-1-j], if j = for 0 ~ i-1
*/

#include <string>
#include <vector>

using namespace std;

typedef long long ll;

int solution(int n) {
    //dp 선언
    vector<ll> dp(n+1, 0);

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

1. 올바른 괄호 쌍으로 만들 수 있는 문자열의 개수 = C(n)
2. 점화식: DP[n] = Σ(DP[i] × DP[n-1-i]) for i = 0 to n-1, i쌍의 괄호로 만들 수 있는 올바른 괄호 문자열의 개수
3. 풀이: i ~ j 구간에서, DP[j]는 i까지 존재하는 올바른 괄호 쌍의 개수에 나머지 dp[j-1-i]까지의 개수를 곱해준 값이다.
4. 기저 조건: DP[0] = 1

 

---