63. 모든 괄호쌍 출력하기 - 카탈란 수 알고리즘

1. 개요

모든 괄호쌍 알고리즘은 카탈란 수 알고리즘에 속함.

카탈란 수 알고리즘이란 점화식이 다음과 같은 모습을 지닐 때를 지칭함.

Cn = 시그마(0 ~ n-1) Ci * Cn-1-i

이렇게 표현하면 정말 수학적 기호도 없고 너무 어려워 보이기에 쉽게 말로 표현하면

한 가지 경우를 시행하면, 그와 쌍이되는 다른 경우를 반드시 시행해야 하는 모든 개수.

말 또한 어렵기 때문에 괄호쌍을 예를들면,

만약 ( 괄호가 나오면 반드시 ) 괄호가 나와야 함. 

( 이 두 번 나오면 ) 도 반드시 두 번 나와야 함.

이처럼 쌍을 이루는 것들을 나열하는 모든 경우의 수를 카탈란 수라고 한다.

괄호쌍 알고리즘도 이에 속하며, 괄호쌍 2개로 예를들면 다음과 같다.

( ( ) )

( ) ( )

단, 이 두 가지 경우뿐이다.

카탈란 수의 정확한 수학적인 성질은 알 수 없지만, 카탈란 수를 나타내는 경우들이 2개 더 있다.

(1) 첫 번째는 2차원 배열에서 한 지점 A에서 B까지 가는 최단경로의 수다.

왜냐하면, A에서 B지점까지 최단경로로 도착하기 위해선 단 두 가지 방향의 쌍으로 이루어진다.

가장 간단히 다음과 같은 배열이 있다.

0 0 B

0 0 0

A 0 0

여기서 A에서 B로 최단경로로 도착하려면, 오른쪽아니면 위쪽 밖에 길이 없다. 그리고 반드시 이 방향은 대칭된다.

그렇기에 카탈란 수에 속한다.

(2) n개의 노드로 이루어진 이진 탐색트리(Binary Search Tree)

괄호쌍이나 2차원 배열 최단경로 수랑은 조금 다르다. 왜냐하면 자식노드의 왼쪽 오른쪽 쌍의 개수가 대칭을 이루지는

않는다. 하지만, 다음의 예를보면

왼쪽 자식 노드 0개, 오른쪽 자식 노드 n-1개.

왼쪽 자식 노드 1개, 오른쪽 자식 노드 n-2개.

왼쪽 자식 노드 2개, 오른쪽 자식 노드 n-3개.

..................

왼쪽 자식 노드 n-1개, 오른쪽 자식 노드 0개.

트리의 구조가 대칭쌍을 이루기에 카탈란 수에 속한다.

2. 문제

2-1) 입력한 괄호쌍 개수에 따른 경우를 모두 출력하는 알고리즘을 작성하시오.

2-2) 카탈란 수를 알고리즘을 작성하시오.

3. 코드 및 출력

3-1) 괄호쌍 코드

3-2) 괄호쌍 출력

3-3) 카탈란 수 코드

3-4) 카탈란 수 출력

4. 정리

이것으로 3장까지 독파했다. 내일부턴 4장.

참 시간은 많은데, 시간이 왜캐 부족하게 느껴질까.

주어진 시간동안 파이팅.