테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » PS / Algorithm » 카탈랑 수 (Catalan number)
ps:카탈랑_수

카탈랑 수 (Catalan number)

  • 카탈란 수라고 표기하는 책도 많은 것 같은데, 여기서는 위키피디아를 따라서 카탈랑수로 표기한다
  • 올바른 괄호의 갯수를 비롯 많은 문제의 해가 카탈랑 수로 표현된다.
  • 그 문제들에 대해서 DP적인 마인드로 접근하면 이런 점화식을 얻는다
    • $ \begin{align} &C_0 = 1 \\ &C_{n+1} = \sum_{i+j=n} C_iC_j \end{align}$
  • 이대로 점화식대로 계산해서 풀려면 O(n^2)이지만, 점화식을 잘 변환하면 다음처럼 식이 정리된다.
    • $ C_n = \frac{1}{n+1}{2n \choose n} $
      • 변환 과정은 간단하지는 않다. 과정을 보려면 나무위키 참조.
    • 이런 변환 없이 이 식을 직관적으로 얻을 수 있는 다른 방법은, 주어진 문제가 딕 경로 문제와 동치임을 이해한 뒤, 딕 경로 문제의 해가 이렇게 됨을 유도하는 것이다.
    • 이 일반항은, 스털링 근사를 적용해서 정리하면 $ O(4^n / n^{\frac{3}{2}}) $ 이다
  • 이렇게 이항 계수 형태의 식을 이용하면 Cn을 O(n)에 구할 수 있다. Cn % P 를 구하는 것도 O(n + logP)에 가능. 자세한 것은 이항 계수참고.
  • 만약 1≤i≤n 까지의 모든 Ci를 구해야 할 경우에는 $ C_{n+1} = \frac{2(2n+1)}{n+2}C_n $ 의 점화식을 사용해서 여전히 O(n)에 모두 구할 수 있다. Ci % P를 구하는 경우도, n 이하의 모든 수의 모듈러 역원을 O(n)에 구하는 방법을 사용하면, 여전히 O(n)에 계산 가능하다.
    • inv = [0, 1]
for i in range(2, MAX_SIZE + 3):
    inv.append(-(MOD // i) * inv[MOD % i])
catalan_nums = [1]
for i in range(MAX_SIZE):
    catalan_nums.append(2 * (2 * i + 1) * inv[i + 2] * catalan_nums[i] % MOD)

관련 문제

토론

댓글을 입력하세요:
T Y U T C
 
ps/카탈랑_수.txt · 마지막으로 수정됨: 2021/01/21 15:37 저자 teferi