#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
'알고리즘' 카테고리의 다른 글
[알고리즘]#12_차분 배열, 2차원 배열의 O(k+n*m)의 범위 업데이트 (1) | 2025.07.22 |
---|---|
[알고리즘]#10_MiniMax, 최적의 의사 결정 (0) | 2025.04.23 |
[알고리즘]#9_Quick Select (0) | 2024.04.30 |
[알고리즘]#7_LCA(Least Common Ancestor) (0) | 2024.03.12 |
[알고리즘]#7_투 포인터 (0) | 2023.12.13 |