카탈란 수란?

카탈란 수(Catalan number)란, 이진 트리의 수를 셀 떼 등장하는 수열이다.

 

응용으로는, 

1. 올바른 괄호쌍 개수: 프로그래머스 올바른 괄호의 개수
2. 이진 트리의 수: 노드 n개를 가진 서로 다른 이진 탐색 트리(BST)의 수
3. 다각형의 삼각분할: n+2변짜리의 다각형을 삼각형으로 분할하는 경우의 수

 

 

https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98