카탈란 수

카탈란 수는 다양한 수학적 문제와 컴퓨터 과학 알고리즘에서 자주 나타나는 수이다.

Cn = C0 * Cn-1 + C1 * Cn-2 + .... + Cn-1 * C0이라는 공식을 가지고 있다.

대표적인 문제 몇가지이다.

• 오일러의 삼각형(n+2의 도형을 삼각형으로 분할하는 경우의 수)
• 알파벳에 괄호 넣기(n+1개의 문자사이에 괄호 넣는 경우의 수)
• 연쇄행렬곱셈 문제(곱셈의 순서가 가질 수 있는 경우의 수)
• Dyck 경로 (n*n개의 격자에서 절반을 갈 수 없을 때 경우의 수)

 

프로그래머스 올바른 괄호의 개수 문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

경우의 수를 계산하는 대표적인 카탈란 수 문제이다.

N:0 

N:1 ()

N:2 (()), ()() => 안1밖0, 안0밖1

N:3 ((())), (()()), (())(), ()(()),()()() => 안2밖0, 안1밖1, 안0밖2

public long catalanDP(int n) {
    long[] catalan = new long[n + 1];
    catalan[0] = 1;

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

    return catalan[n];
}