카탈랑 수

카탈랑 수(Catalan number)는 

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, ... 로 이루어진 수열로,

조합론에서 빈번하게 나타나는 수열이다.

 

점화식으로 나타내면 다음과 같다.

$$ C_{0} = 1, \, C_{n+1} = \sum_{i=0}^{n}{C_{i}C_{n-i}} \; (n \geq 1) $$

 

이 점화식을 따르는 대표적인 예제로, 'n개의 괄호 쌍으로 나타낼 수 있는 올바른 괄호 조합 구하기'가 있다.

(이때 올바른 괄호란, '('의 개수가 항상 많거나 같다가 마지막엔 '('의 개수와 ')'의 개수가 같은 식을 말한다.)

 

점화식을 위해 C(0) = 1이라고 설정한다.

1개의 괄호 쌍

1개의 괄호 쌍은 '()'으로 1개다.

$$C_{1} = 1 $$

 

2개의 괄호 쌍

기본적으로 한 쌍의 괄호가 있다고 할 때, 괄호 1개를 더 추가하는 방법은 2가지다.

 

안에 0개, 밖에 1개의 괄호 추가: ()()
$$C_{0}C_{1} = {1} \times {1} = {1} $$

안에 1개, 밖에 0개의 괄호 추가: (())
$$C_{1}C_{0} = {1} \times {1} = {1} $$

 

위의 경우는 둘 중 하나만 일어나면 되므로 합의 법칙을 적용한다.

따라서 2개의 괄호를 표현하는 경우의 수는 다음과 같다.

$$C_{2} = C_{0}C_{1} + C_{1}C_{0} = {2} $$

 

3개의 괄호 쌍

기본적으로 한 쌍의 괄호 ()가 있다고 할 때, 괄호 2개를 더 추가하는 방법은 3가지다.

 

안에 0개, 밖에 2개의 괄호 추가: ()()() , ()(())
$$C_{0}C_{2} = {1} \times {2} = {2} $$

안에 1개, 밖에 1개의 괄호 추가: (())()
$$C_{1}C_{1} = {1} \times {1} = {1} $$

안에 2개, 밖에 0개의 괄호 추가: ((())) , (()())
$$C_{2}C_{0} = {2} \times {1} = {2} $$

 

따라서 3개의 괄호를 표현하는 경우의 수는 다음과 같다.

$$C_{3} = C_{0}C_{2} + C_{1}C_{1} + C_{2}C_{0} = {5} $$

 

---

일반화하면,

n+1개의 괄호 쌍 조합은 한 쌍의 괄호를 기준으로 안에 i개의 괄호 쌍과 바깥에 n-i개의 괄호 쌍을 추가하면 된다.

(이 때 i는 0부터 n까지다.)

$$ C_{n+1} = \sum_{i=0}^{n}{C_{i}C_{n-i}} $$

 

재귀함수로 카탈랑 수 점화식을 구현한 코드는 다음과 같다.

public static int catalan(int n) {
    int result = 0;
 
    if (n <= 1) {
        return 1;
    }
 
    for (int i = 0; i < n; i++) {
        result += catalan(i) * catalan(n - 1 - i);
    }
    
    return result;
}
 

 

DP로 카탈랑 수 점화식을 구현한 코드는 다음과 같다.

public static int catalan(int n) {
    int[] c = new int[n + 1];
    c[0] = 1;
 
    for (int x = 1; x <= n; x++) {
        for (int i = 0; i <= x - 1; i++) {
            c[x] += c[i] * c[x - 1 - i];
        }
    }
 
    return c[n];
}

 

 

카탈랑 수는 조합론을 통해 간단히 일반식으로도 나타낼 수 있다.

 

$$ C_{n} = \frac{1}{n+1} {{2n} \choose {n}} = \frac{(2n)!}{(n+1)!\,n!} $$

 

참고로 이 식의 증명은
(0,0)에서 (n,n)까지 격자점을 지나는 최단거리의 경로 중에서

직선 y=x를 넘지 않는 경로의 개수를 구하는 것으로 가능하다.

 

카탈랑 수 일반식을 구현한 코드는 다음과 같다.

public static int catalan(int n) {
    long result = 1;
 
    for (int i = n + 2; i <= 2 * n; i++) {
        result *= i;
    }
    for (int i = 1; i <= n; i++) {
        result /= i;
    }
 
    return (int)result;
}

---

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

위 링크는 프로그래머스에서 올바른 괄호의 개수를 구하는 문제이다.

 

각 방법으로 풀었을 때 걸린 시간과 메모리는 다음과 같다.

재귀함수(점화식): 10.91ms, 102MB

DP(점화식): 0.02ms, 74.1MB

일반식: 0.03ms 73.5MB

 

점화식 DP는 시간복잡도가 O(n^2)이고 일반식은 시간 복잡도가 O(n)이라서

일반식이 훨씬 빠를 줄 알았는데 오히려 DP가 살짝 더 빨랐다.

점화식을 DP로 구현하거나 일반식을 구현하는 방법 중 취향에 맞게 선택하면 될 것 같다.

(나는 조금 더 직관적인 점화식 DP 버전을 사용할 것 같다.)

 

 

🔍 그럼 이 카탈랑 수는 어떤 문제에 적용 가능한가?

• n개의 괄호 쌍의 수식 조합
      ((()))    (()())    (())()    ()()()    ()(())
  
  
• 길이가 2n인 뒤크 단어(dyck word)의 개수
  뒤크 단어는 n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 즉 괄호 쌍 조합은 X가 '(' 이고 Y가 ')' 인 특정 케이스라고 볼 수 있다.
      XXXYYY   XYXXYY    XYXYXY    XXYYXY    XXYXYY
  
  
• leaf 노드가 n+1개인 서로 다른 포화 이진 트리의 개수 (= 자식을 가진 노드가 n개인 서로 다른 포화 이진 트리의 개수)

 

• n+1개의 항에 괄호를 씌울 수 있는 조합 (= n+1개의 항에 이항 연산을 적용하는 순서의 모든 경우의 수)
      ((ab)c)d    (a(bc))d    (ab)(cd)    a((bc)d)    a(b(cd))
  
  
• n+2각형을 n개의 삼각형으로 나누는 방법의 수