https://leetcode.com/problems/unique-binary-search-trees/
처음 이 문제를 봤을때 backtracking 으로 가능한 node들을 모두 생성하는 방법으로 접근했습니다.
우선 left 로 갈 수 있는 numbers, right로 갈 수 있는 numbers, 그리고 양쪽으로 node가 추가될 수 있는 경우를 고려해서 구현했습니다.
하지만, 마지막 양쪽으로 node 가 추가될 수 있는 경우에서 node 가 추가될때 binary search Tree에 대한 validation 을 다시 진행해야합니다
(https://leetcode.com/problems/validate-binary-search-tree/description/ , 리트코드 98번)
결국 이번 문제는 솔루션을 참고 했습니다.
솔루션을 참고하는 중 카탈란 수(Catalan number) 에 대해 알게되어 카탈란 수 관련해서 남겨놓습니다.
카탈란 수
카탈란 수는 여는 괄호 n개와 닫는 괄호 n개로 구성된 올바른 괄호 문자열의 개수를 나타내는 수입니다.
( https://leetcode.com/problems/longest-valid-parentheses/ 리트코드 32번도 관련됨)
여는 괄호와 닫는 괄호의 조합에서도 사용할 수 있지만 특정한 트리 구조의 개수를 셀때도 카탈란 수를 이용 할 수 있습니다.
카탈란 수 n 은 노드 n 개로 구성된 트리의 개수와 같습니다.
( 지금 풀고 있는 리트코드 96번의 풀이와 완전 일치합니다)
카탈란 수는 점화식이 존재하기 때문에 DP 문제로 접근해서 풀 수 있습니다. (n 이 충분히 크다면 메모이제이션을 활용하지 않을경우 풀 수 없습니다)
python 코드로는 아래와 같이 풀 수 있겠네요.
리트코드 96번은 카탈란 수 풀이와 정확히 일치하므로 카탈란 수만 찾을 수 있으면 쉽게 풀수 있는 문제입니다.
리트코드 32번을 풀 때 단순 풀이만이 아닌 카탈란 수까지 접근 했더라면 이번 문제는 풀 수 있었는데 조금 아쉬움이 느껴져서 카탈란 수까지 정리합니다.
(조합론에서 많이 사용하는 수라고 합니다)
참고 : 알고리즘 트레이닝( http://www.yes24.com/Product/Goods/72274740 )