무언가를 세는 문제에서 광범위하게 나타나는 숫자가 있습니다. 카탈란 넘버Catalan number라고 부르는 이 숫자들은 다음과 같은 수열, 즉 시퀀스sequence입니다.

1, 1, 2, 5, 14, 42, 132, 429, 1430, \dots

이 숫자들이 무엇이 특별할까요?

바이너리 트리binary tree의 개수를 세다보면 카탈란 넘버를 마주치게 됩니다. 노드가 하나인 바이너리 트리는 1가지, 두 개는 2가지, 세 개는 5가지가 있습니다.

Five kinds of binary trees with three nodes — 그림 1. 세 노드를 가진 트리들. 총 5가지가 존재합니다.

나아가서 노드가 네 개라면 14가지, 다섯 개라면 42가지가 있습니다.

카탈란 넘버 $C_n$ 는 다음과 같은 점화식recurrence relation으로 정의할 수 있습니다.

\begin{align*} C_n &= \sum_{k=0}^{n-1} C_k C_{n-1-k} \quad (C_0 = 0) \\ &= C_0 C_{n-1} + C_1 C_{n-2} + C_2 C_{n-3} + \cdots + C_{n-1} C_0 \end{align*}

다시 말해, 노드가 $n$ 개인 바이너리 트리는 $C_n$ 가지인 것입니다. 그리고 점화식을 얻었으므로, 간단한 코드를 통해 그 개수를 계산할 수 있습니다.

그런데 왜 바이너리 트리의 개수가 이런 점화식을 가질까요? 문제를 더 작은 문제의 답을 통해 푸는 패턴과 관련이 있습니다. 점화식에서 $C_n$ 을 구하기 위해 $C_0$ 을 비롯한 이전 카탈란 넘버를 쓰는 부분에서 볼 수 있습니다.

앞으로 소개할 내용을 통해, 트리의 개수를 계산하는 방법이 카탈란 넘버 점화식의 모습에 고스란히 반영되고 있다는 사실을 알게 될 것입니다. 그리고 한번 그 계산 방법을 배우고 나면, 언뜻 전혀 상관없어 보이는 다른 많은 문제에도 똑같이 적용할 수 있다는 것을 볼 수 있습니다.

일일이 세는 대신 패턴을 세기

노드가 네 개일 땐 바이너리 트리가 14가지라고 앞서 언급했습니다. 그런데 어떻게 구할 수 있을까요?

재밌는 소식을 미리 언급하자면 카탈란 넘버는 대략 $4^n$ 을 따라 가파르게 커지기 때문에, 노드가 조금만 많아져도 일일이 세기가 금방 어려워집니다.

하지만 그렇게 하지 않고, 이미 풀었던 문제의 답으로 해결할 수 있습니다. 왼쪽 서브트리subtree에 시선을 고정해두고, 여기에 오는 노드 개수를 기준으로 케이스를 나눠봅시다.

Four cases of binary tress with four nodes — 그림 2. 노드가 네 개일 때의 패턴. 왼쪽 서브 트리에 몇 개의 노드가 있는 지에 따라 나눕니다.

노드가 $n$ 개일 때 트리의 개수를 $C_n$ 이라고 해봅시다. 첫 번째 경우, 왼쪽에 $C_0$ 가지, 오른쪽에 $C_3$ 가지가 올 수 있기 때문에, 총 $C_0 \times C_3$ 가지의 트리를 만들 수 있습니다. 이런 식으로 나머지 경우도 구할 수 있습니다.

결국 네 개의 노드로 만들 수 있는 트리의 개수 $C_4$ 는 다음과 같이 계산할 수 있게 됩니다.

C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 14

이것을 노드가 $n$ 개인 경우로 쉽게 일반화할 수 있습니다.

C_n = C_0 C_{n-1} + C_1 C_{n-2} + C_2 C_{n-3} + \cdots + C_{n-1} C_0

그러면 앞서 소개했던 카탈란 넘버의 점화식이 나타납니다.

악수 문제에서 찾아내는 똑같은 패턴

똑같은 해결 패턴이 다음과 같은 악수 문제에서도 나타납니다. 악수 문제란 이런 것입니다.

여덟 명의 사람이 둥근 테이블에 있다. 서로 악수를 하려고 하지만, 팔이 교차되는 일은 없기를 바라고 있다. 그러면 그런식으로 악수를 하는 방법은 총 몇 가지인가?

Successful and failed case of handshaking — 그림 3. 악수 문제. 왼쪽은 올바른 악수입니다. 하지만 오른쪽처럼 4번과 6번이 악수하면, 5번과 7번이 악수할 때 팔이 교차되므로 잘못된 악수입니다.

이 문제는 처음 보면 어려워보이지만, 해결 방법은 알고보면 트리 개수 세기만큼 간단합니다. 여기서도 더 작은 문제의 답을 이용해 풀 수 있기 때문입니다.

이번에는 1번 사람이 누구와 악수하는지 기준으로 케이스를 나눠봅시다.

Handshaking diagram — 그림 4. 악수의 네 가지 패턴. 1번 사람이 누구와 악수를 하는 지에 따라 나눕니다. 3번 사람과 악수한다면, 2번 사람은 악수할 사람이 없게 됩니다. 이런 이유로 홀수 번의 사람과 악수하는 경우는 생각할 필요가 없습니다.

그러면 1번과 악수한 팔이 사람들을 두 그룹으로 나눕니다. 따라서 악수하는 방법의 수는 각 그룹에서 악수하는 방법의 수를 곱한 것이 됩니다.

$n$ 명이 악수하는 방법의 수를 $H_n$ 이라고 해봅시다. 그러면 문제의 답 $H_8$ 은 이렇게 됩니다.

H_8 = H_0 H_6 + H_2 H_4 + H_4 H_2 + H_6 H_0

여기서 $C_n = H_{2n}$ 으로 정의해봅시다.

C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0

따라서 이 문제의 답은 또 카탈란 넘버가 됩니다.

카탈란 넘버 계산 프로그램

점화식을 구했으니, 실제로 카탈란 넘버를 계산할 수도 있을 것입니다.

def catalan(n)
  if n == 0:
    return 1

  ans = 0
  for k in range(n):
    ans += catalan_bf(k) * catalan_bf(n-1-k)
  return ans

파이썬Python으로 구현하면 이렇게 됩니다. 시간 복잡도가 $O(3^n)$ 인 점은 언급만 하고, 증명은 직접 해보는 문제로 남기겠습니다.

그런데 위 코드는 똑같은 카탈란 넘버를 여러번 계산하는데요. 이런 중복 계산은 이미 계산한 결과를 재사용하는 다이나믹 프로그래밍dynamic programming으로 피할 수 있습니다.

def catalan(n)
    dp = [0] * (n+1)
    dp[0] = 1

    for m in range(1, n+1):
        for k in range(m):
            dp[m] += dp[k] * dp[m-1-k]

    return dp[n]

시간 복잡도 또한 $O(n^2)$ 으로 줄어들게 됩니다.

위 코드는 지스트Gist에서도 볼 수 있습니다.

마치며

카탈란 넘버는 앞서 본 문제 외에도, 괄호를 짝을 맞춰 나열하는 방법, 다각형을 삼각형으로 쪼개는 방법 등 겉보기에 관련이 없어보이는 곳에서도 나타납니다. 이런 문제들이 왜 본질적으로 같은 문제인지 나중에 살펴보도록 하겠습니다.

그리고 마지막에 만들어봤던 카탈란 넘버 계산 프로그램이 더 나은 시간 복잡도 $O(n)$ 을 갖도록 개선할 수 있습니다. 카탈란 넘버는 $C_n = \frac{4n-2}{n+1} C_{n-1}$ 라는 점화식도 가지기 때문에, $n$ 번의 계산으로 카탈란 넘버를 구할 수 있기 때문입니다. 이런 점화식이 나타나는 이유 또한 다음에 살펴보겠습니다.

레퍼런스

Catalan Numbers (Richard Stanley, 2015)
Catalan Numbers, Recursive function time complexity (Stackoverflow): 카탈란 넘버 계산 알고리즘의 시간 복잡도 $O(3^n)$ 의 증명을 담고 있습니다.