파이썬으로 n번째 카탈란 수(Catalan Number) 구하기

이 글에서는 n번째 카탈란 수(Catalan Number)를 계산하는 방법을 알아봅니다.

카탈란 수란 무엇인가?

카탈란 수는 조합론에서 매우 중요하게 다뤄지는 자연수 수열입니다. 올바른 괄호 문자열의 개수, 만들 수 있는 이진 트리의 개수, 볼록 다각형을 삼각형으로 나누는 방법의 수 등 다양한 문제에서 등장합니다.

카탈란 수는 다음과 같은 재귀적 점화식으로 정의됩니다.

C₀ = 1 이고, C_n+1 = Σⁿ_i=0 C_i · C_n−i (n ≥ 0)

즉, n번째 카탈란 수는 그보다 작은 카탈란 수들의 곱의 합으로 표현됩니다. n = 0, 1, 2, 3, … 에 해당하는 처음 몇 개의 카탈란 수는 다음과 같습니다.

1, 1, 2, 5, 14, 42, 132, 429, …

카탈란 수는 재귀 호출과 동적 프로그래밍, 두 가지 방법으로 구할 수 있습니다. 각각의 구현 방법을 살펴보겠습니다.

방법 1: 재귀 함수를 이용한 구현

정의된 점화식을 그대로 코드로 옮기는 가장 직관적인 방법입니다.

# 재귀적 해법
def catalan(n):
    # n이 0 또는 1이면 기저 사례
    if n <= 1:
        return 1
    # catalan(n) = catalan(i) * catalan(n-i-1)
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n - i - 1)
    return res

# 실행
for i in range(6):
    print(catalan(i))

출력 결과

이 방법은 점화식을 충실히 반영하지만, 이미 계산한 하위 문제를 반복해서 다시 계산하기 때문에 시간 복잡도가 지수적으로 증가합니다. 따라서 n이 커질수록 매우 비효율적이라는 단점이 있습니다.

방법 2: 동적 프로그래밍을 이용한 구현

동적 프로그래밍(DP)은 한 번 계산한 결과를 테이블에 저장해 두었다가 재사용함으로써 중복 계산을 없애는 기법입니다. 위 재귀 방식의 비효율을 크게 개선할 수 있습니다.

# 동적 프로그래밍 활용
def catalan(n):
    if n == 0 or n == 1:
        return 1
    # 테이블 생성 및 초기화
    catalan = [0] * (n + 1)
    catalan[0] = 1
    catalan[1] = 1
    # 점화식 적용
    for i in range(2, n + 1):
        for j in range(i):
            catalan[i] += catalan[j] * catalan[i - j - 1]
    return catalan[n]

# 실행
for i in range(6):
    print(catalan(i), end=" ")

출력 결과

1 1 2 5 14 42

동적 프로그래밍 방식은 시간 복잡도가 O(n²)로, 지수적으로 증가하는 순수 재귀 방식보다 훨씬 효율적입니다. 또한 이항계수를 이용하면 C_n = (2n)! / ((n+1)! · n!) 공식으로 한 번의 계산으로도 구할 수 있습니다.

마무리

이 글에서는 카탈란 수의 정의와 함께, 재귀 함수와 동적 프로그래밍 두 가지 방법으로 n번째 카탈란 수를 구하는 방법을 배웠습니다. 작은 입력에는 재귀 방식으로 충분하지만, 성능이 중요한 상황에서는 중복 계산을 제거하는 동적 프로그래밍 방식을 사용하는 것이 좋습니다.