카탈란수의 활용

이전 글에서 카탈란 수는 적당한 대응을 통해 많은 문제를 푸는 데 사용할 수 있다고 하였다.

그 문제들의 목록은 다음과 같다.

이 글에서는 각 문제를 카탈란 수에 대응시키는 방법에 대해 알아보겠다.

1. 경로의 수 문제

이 문제는 이전 글에서 다루었으니 넘어가겠다.

2. 한 요소가 다른 요소보다 항상 크게 유지하는 문제

같은 개수의 X와 Y를 활용해 만드는 단어 중 단어의 처음에서 X와 Y의 개수를 셌을 때 항상 X의 개수가 Y의 개수 이상인 단어의 개수를 구하여라.

이 문제는 경로의 수 문제로 대응하여 카탈란 수로 대응할 수 있다. 길이가 $2n$인 단어를 만들기 위해 X $n$개, Y $n$개를 사용한다.

이 상황을 (0, 0)에서 (n, n)까지 격자점만을 지나 도착하는 경우로 생각하면 X는 오른쪽으로, Y는 위쪽으로 이동하는 것으로 보고, "항상 X의 개수가..."라는 조건은 y=x+1 위를 밟지 않는 조건, 즉 카탈란수로 이해할 수 있다.

따라서 이 문제의 답은 단순히 $C_{n}$이다.

3. 괄호 열고 닫기 문제

$n$개 쌍의 괄호를 쌍이 맞도록 열고 닫는 방법의 수를 구하여라.

쌍이 맞도록 열고 닫는다는 뜻은 곧 여는 괄호('(')의 개수가 항상 닫는 괄호(')')의 개수 이상으로 유지하는 것이다.

예를 들어 다음은 쌍이 맞는 괄호이다.

(()(()))

또한 다음은 쌍이 맞지 않는 괄호이다.
(()))()(

이 상황은 즉, 항상 여는 괄호의 개수가 닫는 괄호의 개수 이상인 상황으로 생각할 수 있다.

즉, 2번 경우로 대응시켜 $C_n$가지의 경우가 있다.

4. 다각형 나누기 문제

$n+2$각형을 $n$개의 삼각형으로 나누는 방법의 수를 구하여라

육각형을 예로 들어보자.

각 변에 a부터 f까지 문자를 매긴다.

이제 육각형을 삼각 분할하고, 분할된 방식대로 각 변의 문자를 괄호로 묶는다.

묶는 규칙은 단순히 2개 이상의 변에 문자가 적혀있는 삼각형을 골라서 각 변의 문자를 괄호로 묶어서 나머지 한 변에 적으면 된다.

그러면 가장 마지막 삼각형에서는 세 변을 모두 괄호로 묶어서 괄호 묶음이 하나 나올 것이다. 이 묶음에서 문자를 지우면 괄호로 이루어진 묶음이 나온다. 그리고 이 쌍은 항상 규칙에 맞는다.

즉, 하나의 분할은 하나의 괄호 묶음과 대응되고, 괄호 묶음의 개수는 2번에서 설명한 대로 구할 수 있다.

따라서 $n+2$각형을 삼각형으로 분할하는 경우의 수는 $C_n$가지이다.

5. 이진트리 문제

단말 노드(자식이 없는 노드)가 $n$개인 이진트리의 개수를 구하여라.

우선 이진트리에 대해 간단히 설명하자면 이진트리는 다음과 같이 한 노드가 2개 혹은 0개의 자식 노드를 가지는 트리이다. 여기서 노드는 각 A~I 점을 말한다.

이 문제는 2번에서 설명한 괄호 문제로 대응할 수 있다.

각 단말 노드에 a부터 문자를 붙이자.

그리고 각 형제 노드끼리 괄호 쌍으로 묶는다. 가령 H에 해당하는 a와 I에 해당하는 b는 한 괄호로 묶인다.

이러한 방식으로 괄호를 묶으면 하나의 완성된 괄호 쌍이 된다. 예를 들어 위 그림에 그려진 트리는 아래와 같이 된다.

(((ab)c)(de))

이는 곧 트리 하나와 괄호 하나가 대응됨을 의미한다.

따라서 $n$개의 단말 노드를 가지는 트리의 개수는 $C_{n-1}$ 개다.

6. 입출력 문제

문자 $n$개를 충분히 큰 크기의 버퍼에 순서대로 입출력하는 경우의 수를 구하여라.

이것도 2번 문제와 같은 문제이다. "버퍼에 입력"의 개수가 "버퍼에 출력"의 개수보다 항상 같거나 커야 한다. 즉 단순히 $C_n$이다.

이 문제는 영화관, 기차 등등 수많은 상황으로 응용될 수 있기 때문에 일반적인 상황으로 알아두는 것이 좋겠다.

티스토리툴바