[프로그래밍 수학] 카탈란 수(catalan number)
이 개념이 적용된 프로그래밍 문제를 풀 때 풀이과정이 흥미로웠다. 이를 다른 사람들과 공유하고 동시에 기록에 남기고 싶어서 이렇게 글을 쓴다. 카탈란 수는 자연수로 이루어진 수열이다. 항을 차례대로 나열하면 아래와 같다. 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, ... 카탈란 수를 C_n이라고 하고 이를 점화식으로 표현하면 이를 조합으로 표현하면 이 조합은 어떻게 얻어진 것일까? 나는 카탈란 수라는 개념을 주어진 key로 만들 수 있는 Binary Search Tree의 개수를 구하는 문제에서 처음 접했다. https://soccer-programming.tistory.com/15 Program to find the ..
2020. 4. 5.
