괄호

카탈란수의 활용

이전 글 이전 글에서 카탈란 수는 적당한 대응을 통해 많은 문제를 푸는 데 사용할 수 있다고 하였다. 그 문제들의 목록은 다음과 같다. 경로의 수 문제 다각형 나누기 문제 이진트리 문제 괄호 열고 닫기 문제 입출력 문제 한 요소가 다른 요소보다 항상 크게 유지하는 문제 이 글에서는 각 문제를 카탈란 수에 대응시키는 방법에 대해 알아보겠다. 1. 경로의 수 문제 이 문제는 이전 글에서 다루었으니 넘어가겠다. 설명 2. 한 요소가 다른 요소보다 항상 크게 유지하는 문제 같은 개수의 X와 Y를 활용해 만드는 단어 중 단어의 처음에서 X와 Y의 개수를 셌을 때 항상 X의 개수가 Y의 개수 이상인 단어의 개수를 구하여라. 이 문제는 경로의 수 문제로 대응하여 카탈란 수로 대응할 수 있다. 길이가 $2n$인 단어를..