1. 카탈랑 수(Catalan Number)란?

조합수학에서 자주 등장하는 대표적인 수열 중 하나로, "특정 제약 조건을 침범하지 않으면서 순서대로 조합을 만들어내는 경우의 수"를 의미합니다.

• 수열 값: $1, 1, 2, 5, 14, 42, 132, \dots$

• 핵심 조건: 진행 과정 중 어느 지점에서든 상태 A의 누적량이 상태 B의 누적량보다 적어서는 안 된다 ($A \ge B$)는 제약이 걸려 있습니다.

• 또는 큰 문제를 작은 문제 2개로 나누어 풀 수 있을 때 사용 가능

---

2. 카탈랑 수가 적용되는 4대 대표 문제

문장과 상황은 전혀 달라 보이지만, 수학적으로 완전한 동형(Isomorphic) 구조를 가집니다.

문제 유형	상황 설명	예시 ($n=3$)
1. 올바른 괄호	$n$쌍의 (와 )로 만드는 올바른 괄호 문자열 개수	((())), (()()), (())(), ()(()), ()()() $\rightarrow$ 5개
2. 이진 트리 개수	$n$개의 노드로 만들 수 있는 서로 다른 이진 트리의 개수	루트 노드 기준 좌/우 자식 배치 고려 $\rightarrow$ 5개
3. 대각선 안 넘기	$n \times n$ 격자에서 대각선($y=x$)을 넘지 않고 (0,0)에서 (n,n)까지 가는 최단 경로	오른쪽(R), 위(U) 이동 중 $U \le R$ 유지 $\rightarrow$ 5개
4. 볼록 다각형 분할	$(n+2)$각형을 교차하지 않는 대각선으로 삼각 분할하는 방법 수	오각형($n=3$)을 삼각형 3개로 쪼개기 $\rightarrow$ 5개

---

3. DP 점화식과 도출 원리: ( A ) B 분해법

분해 아이디어

맨 처음 나오는 (와 짝이 되는 )의 위치를 기준으로 전체 문자열을 강제로 쪼개어 중복을 방지합니다.

$\text{(} + [\text{안쪽 괄호 A}] + \text{)} + [\text{바깥쪽 괄호 B}]$

1. 전체 $n$쌍 중 맨 앞 (와 짝 )로 1쌍을 사용합니다.
2. 남은 $n-1$쌍을 안쪽 $A$와 바깥쪽 $B$에 나누어 배치합니다.
3. 안쪽 $A$에 $i$쌍을 배치하면, 바깥쪽 $B$에는 $n - 1 - i$쌍이 들어갑니다.

점화식 (Recurrence Relation)

$dp[n] = \sum_{i=0}^{n-1} dp[i] \times dp[n - 1 - i] \quad (dp[0] = 1, dp[1] = 1)$

---

4. 조합 공식과 대칭의 법칙 (Reflection Principle)

조합 공식 (Combinatorics Formula)

$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}$

증명 핵심 아이디어 (대칭의 법칙)

$n \times n$ 격자 최단 경로 문제를 기준으로 공식을 유도할 수 있습니다.

1. 전체 경로 개수: $2n$번의 이동 중 $n$번 위로 가야 하므로 $\binom{2n}{n}$
2. 실패한 경로(경계 침범): 대각선 위 선분 $y = x + 1$에 최소 한 번 이상 닿은 경로
3. 대칭 변환: 첫 접점 이후의 경로를 $y = x + 1$ 선을 기준으로 반대로 뒤집으면, 모든 실패 경로가 (0,0)에서 (n-1, n+1)로 가는 경로와 1:1 대응됩니다.
4. 실패한 경로 개수: $\binom{2n}{n-1}$

$\therefore C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}$

---

5. C++ 실전 구현 코드 (DP 방식)

$n$이 소규모($n \le 19$)일 때 안전하게 $O(n^2)$ 시간 복잡도로 구하는 DP 코드입니다.

#include <vector>

using namespace std;

long long solution(int n) {
    vector<long long> dp(n + 1, 0);
    
    // Base Case
    dp[0] = 1;
    dp[1] = 1;
    
    // DP 점화식 수행
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    
    return dp[n];
}

---

6. 코딩테스트 실전 전략 요약

1. 패턴 암기: "올바른 괄호 개수", "이진 트리 개수", "대각선을 넘지 않는 최단 경로" 문제 $\rightarrow$ 카탈랑 수 문제로 판단
2. 풀이 선택:

• $n \le 20$: DP 점화식 사용 ($O(n^2)$)
• $n$이 크거나 모듈러 연산 필요: 조합 공식 $\frac{1}{n+1}\binom{2n}{n}$ 사용 ($O(n)$)