사용자 도구

사이트 도구


ps:선형_점화식

선형 점화식

상수계수의 선형 점화식 (동차 선형 점화식)

  • DP에서 얻어진 점화식이 dp[n] = c[1]*dp[n-1] + c[2]*dp[n-2] + … + c[d]*dp[n-d] 형태일 경우 상수계수의 선형 점화식 이라고 불린다
    • 대표적인 예로 피보나치 수열이 있다
  • 일반적인 DP를 이용하면 O(n) 시간에 풀 수 있지만, 행렬의 거듭제곱을 이용해서 O(logn)에 푸는 방법이 있다.
  • 인접 3항간의 점화식, dp[n] = a*dp[n-1] + b*dp[n-2] 에 대한 경우를 예로 들면
    • $ \begin{bmatrix}dp[n] \\ dp[n-1] \end{bmatrix}=\begin{bmatrix}a & b \\1 & 0 \end{bmatrix}\begin{bmatrix}dp[n-1] \\ dp[n-2] \end{bmatrix} $ 으로 쓸 수 있으니까
    • $ \begin{bmatrix}dp[n] \\ dp[n-1] \end{bmatrix}=\begin{bmatrix}a & b \\1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix}dp[1] \\ dp[0] \end{bmatrix}$ 이 된다
  • 중간에 있는 행렬의 (n-1)승을 구하는 것은, 일반적인 거듭제곱 알고리즘과 마찬가지 방식으로 O(logn)에 구할 수 있다.
  • 더 많은 인접항에 대한 점화식도 같은 방식으로 풀 수 있다.
  • 생성함수를 이용하면 행렬이 포함되지 않은 형태로 일반항을 구할수도 있지만, 일반항 안에 무리수의 거듭제곱이 포함되게 되어서, 일반항으로 부터 계산하는 것이 행렬로 계산하는 것보다 시간복잡도는 나아지지 않고 구현만 복잡해진다.

키타마사법

  • 위의 식에서 d가 커지면, 행렬 계산에 드는 시간도 고려해야 한다. dxd 행렬을 단순히 곱하는 데에는 O(d^3)이므로, 복잡도가 O(d^3 * logn)이다.
    • 그냥 행렬을 안쓰고 계산하면 O(d*n)
  • 키타마사법은 이것을 O(d^2 * logn)으로 줄일 수 있는 방법을 제공한다.

코드

대표적 예제

토론

댓글을 입력하세요:
R Z D J P
 
ps/선형_점화식.txt · 마지막으로 수정됨: 2021/01/22 14:49 저자 teferi