이 글에서는 파이썬을 이용해 N번째 카탈란 수(Catalan Number)를 계산하는 방법을 알아봅니다. 재귀 함수를 사용하는 방법과 동적 프로그래밍을 활용하는 방법, 두 가지 접근 방식을 예제 코드와 함께 살펴보겠습니다.
카탈란 수란 무엇인가?
카탈란 수는 다음과 같은 재귀 공식으로 정의되는 자연수 수열입니다.
$$c_{0} = 1\;and\; c_{n+1} = \displaystyle\sum\limits_{i=0}^nc_{i} c_{n-i}\; for n\geq 0 ;$$
n = 0, 1, 2, 3, …에 해당하는 첫 몇 개의 카탈란 수는 다음과 같습니다.
1, 1, 2, 5, 14, 42, 132, 429, …
카탈란 수는 조합론에서 자주 등장하는 유명한 수열로, 올바르게 짝지어진 괄호 문자열의 개수, 볼록 다각형을 삼각형으로 나누는 방법의 수 등 다양한 문제에서 그 값이 활용됩니다. 이 수열은 재귀 호출과 동적 프로그래밍 두 가지 방식으로 모두 구할 수 있으며, 아래에서 각각의 구현 방법을 확인해 보겠습니다.
방법 1: 재귀(Recursion)를 이용한 풀이
재귀 방식은 카탈란 수의 정의식을 그대로 코드로 옮긴 것입니다. catalan(i) × catalan(n-i-1)의 합을 반복문으로 누적하여 값을 구합니다.
# 재귀를 이용한 해법
def catalan(n):
# n이 1 이하이면 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))
출력 결과
1 1 2 5 14 42
재귀 방식은 직관적이라는 장점이 있지만, 같은 값을 여러 번 중복 계산하게 되므로 n이 커질수록 실행 시간이 기하급수적으로 늘어난다는 단점이 있습니다. 따라서 큰 n에 대해서는 비효율적입니다.
방법 2: 동적 프로그래밍(Dynamic Programming)을 이용한 풀이
동적 프로그래밍 방식은 이미 계산한 값을 배열(테이블)에 저장해 두고 재사용함으로써 중복 계산을 제거합니다. 이를 통해 성능을 크게 향상시킬 수 있습니다.
# 동적 프로그래밍을 이용한 해법
def catalan(n):
if n == 0 or n == 1:
return 1
# 결과를 저장할 테이블 생성
catalan = [0 for i in range(n + 1)]
# 초기값 설정
catalan[0] = 1
catalan[1] = 1
# 점화식을 이용해 차례대로 계산
for i in range(2, n + 1):
catalan[i] = 0
for j in range(i):
catalan[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²)로, 재귀 방식의 지수적 시간 복잡도에 비해 훨씬 효율적입니다. n이 큰 경우에는 반드시 이 방법을 사용하는 것이 좋습니다.
마무리
이번 글에서는 카탈란 수의 정의와 함께, 파이썬으로 N번째 카탈란 수를 생성하는 두 가지 방법, 즉 재귀 방식과 동적 프로그래밍 방식을 살펴보았습니다. 작은 입력에는 재귀 방식도 충분하지만, 실무나 코딩 테스트에서는 중복 계산을 줄여 성능을 높인 동적 프로그래밍 방식을 활용하는 것을 추천합니다.