정수 n이 주어졌을 때, 해당 위치에 있는 카탈란 수(Catalan Number)를 구하는 것이 이번 글의 목표입니다. 프로그램 작성에 앞서, 카탈란 수가 무엇인지 먼저 살펴보겠습니다.
카탈란 수는 다양한 조합론(Counting) 문제에서 자연스럽게 나타나는 자연수 수열입니다. 이진 트리, 괄호 배치, 다각형 분할 등 여러 수학적 구조에서 반복적으로 등장하는 것으로 유명합니다.
카탈란 수의 정의와 공식
카탈란 수 C₀, C₁, C₂, … Cₙ은 다음 공식으로 정의됩니다.
$$c_{n}=\frac{1}{n+1}\binom{2n}{n} = \frac{2n!}{(n+1)!n!}$$
n = 0, 1, 2, 3, … 에 대한 카탈란 수의 값은 순서대로 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, … 입니다.
예를 들어 n = 3을 입력하면 프로그램은 5를 출력해야 합니다.
카탈란 수의 대표적인 활용 사례
- n개의 키를 가질 수 있는 이진 탐색 트리(Binary Search Tree)의 개수 세기
- n쌍의 괄호가 올바르게 짝지어진 표현식의 개수 구하기 — 예를 들어 n = 3일 때 가능한 괄호 표현식은 ((())), ()(()), ()()(), (())(), (()()) 입니다.
- 원 위의 점들을 서로 교차하지 않는 현(chord)으로 연결하는 방법의 수 구하기 등
문제 예시
입력: n = 6 출력: 132 입력: n = 8 출력: 1430
문제 해결 접근 방식
- 정수 n을 입력받습니다.
- n <= 1인 경우 1을 반환합니다. (기저 조건)
- i = 0부터 i < n까지 반복문을 실행합니다.
- 각 i마다 result = result + (catalan(i) × catalan(n-i-1)) 을 누적합니다.
- 최종 결과를 반환하고 출력합니다.
알고리즘 단계
시작
Step 1 -> 함수 unsigned long int catalan(unsigned int n)
만약 n <= 1이면,
1을 반환
종료
unsigned long 변수 res = 0 선언
반복문 For i=0, i<n, i++
res = res + (catalan(i)*catalan(n-i-1))
반복문 종료
res 반환
Step 2 -> int main()
입력값 n = 6으로 설정
"catalan is :" 출력 후 catalan(n) 함수 호출
종료C 코드 구현
아래는 재귀(Recursion) 방식을 사용하여 카탈란 수를 구하는 C 프로그램입니다.
#include <stdio.h>
// 재귀 방식으로 카탈란 수를 구하는 함수
unsigned long int catalan(unsigned int n) {
// 기저 조건(Base case)
if (n <= 1) return 1;
// catalan(n)은 catalan(i)*catalan(n-i-1)의 합
unsigned long int res = 0;
for (int i=0; i<n; i++)
res += catalan(i)*catalan(n-i-1);
return res;
}
// 메인 함수
int main() {
int n = 6;
printf("catalan is :%ld\n", catalan(n));
return 0;
}실행 결과
catalan is :132
위 코드는 카탈란 수의 핵심 성질인 cₙ = Σ cᵢ·cₙ₋ᵢ₋₁ 관계를 그대로 재귀로 구현한 것입니다. 다만 이 방식은 중복 계산이 많아 시간 복잡도가 지수적으로 증가하므로, 실제 큰 n을 다룰 때는 동적 계획법(DP)이나 이항계수 공식을 활용하는 것이 더 효율적이라는 점을 참고하시기 바랍니다.