[Python][파이썬][프로그래머스] 올바른 괄호의 갯수(카탈란 수)

programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

 

문제 설명

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

제한사항

• 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

---

입출력 예

n                                                                         result

2	2
3	5

입출력 예 설명

입출력 예 #1
2개의 괄호쌍으로 [ (()), ()() ]의 2가지를 만들 수 있습니다.
입출력 예 #2
3개의 괄호쌍으로 [ ((())), (()()), (())(), ()(()), ()()() ]의 5가지를 만들 수 있습니다.

---

해당 문제는 카탈랑 수를 이용한다.

카탈랑 수의 공식은 다음과 같다

조합론에서의 개수 세기 문제 가운데 많은 것이 카탈랑 수를 그 해로 갖는다. 이 예제들은 조합 수학자 리처드 P. 스탠리의 저서 《Enumerative Combinatorics》 2권[2]에 나오는 카탈랑 수의 서로 다른 66가지 표현 가운데 몇 개를 뽑은 것이다. 

• Cn은 -1과 1 값으로 만들어진 수열 (a1, a2, ..., a2n)에서a1+a2+...+a2n=0 일 때, 각각의 부분합 a1, a1+a2, ..., a1+a2+...+a2n이 모두 0 이상이 되도록 하는 방법의 수이다.
• Cn은 ai가 1 또는 -1일 때, a1+a2+...+a2n+2=0이고 각각의 부분합 a1, a1+a2, ..., a1+a2+...+a2n+1이 모두 0 보다 크게 되도록 하는 방법의 수이다.
• Cn은 길이가 2n인 모든 뒤크 단어(영어: Dyck word)의 개수이다. 발터 폰 뒤크(독일어: Walther von Dyck)의 이름을 딴 뒤크 단어는 n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다.

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• 뒤크 단어에서 X를 여는 괄호로 보고 Y를 닫는 괄호로 보면, Cn은 n쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다. 다음은 n이 4일때의 예시이다.

• Cn은 n + 1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 n + 1개의 항에 이항 연산을 적용하는 순서의 모든 가지수로도 볼 수 있다. 예를 들어 n = 3일 때, 4개의 항에 대해 다섯개의 괄호 표현식이 존재한다.

• 이항 연산의 적용 순서는 이진 트리로도 나타낼 수 있다. 따라서 Cn은 n + 1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다.

• Cn은 동형이 아닌 모든 정 이진 트리 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 n개인 트리의 개수이다. (정 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)
• Cn은 n+2각형을 n개의 삼각형으로 나누는 방법의 수이다. 아래 그림은 6각형을 4개의 삼각형으로 나누는 모든 방법을 나타낸 것으로 총 C4가지이다.

 

카탈랑 식을 구현한 코드는 다음과 같다.

def fac(n):
    if n == 1:
        return 1
    return n * fac(n-1)

def solution(n):
    return fac(2*n)/(fac(n+1) * fac(n))