(WIP) 백준 알고리즘 11444. 피보나치 수 6

첫 포스트: reducing space complexity

https://www.acmicpc.net/problem/11444
제약사항: n은 1,000,000,000,000,000,000보다 작거나 같은 자연수

아래처럼 풀면 메모리 한도 초과 발생.

def f(n):
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

if __name__ == '__main__':
    n = int(input())
    ans = f(n)
    print(ans)

2021/01/03: linear algebra expression, matrix power implementation using memoization

The following equations can be represented by linear algebra.
$f(n+1) = f(n) + f(n-1)$
$f(n) = f(n) + 0$

This can be reduced as below.

$f(1) = 1$ by definition
$f(0) = 0$ by definition

def f(n):
    M0 = [[1, 1],
          [1, 0]]
    X = [[1],[0]]
    M = mat_power(M0, n)
    Y = matmul(M, X)
    # ` % 1000000007` is given by the problem.
    return Y[1][0] % 1000000007

def matmul(M0, M1):
    # output matrix shape
    m, n = len(M0), len(M1[0])
    start = time.time()
    # reserve output matrix
    O = [[0] * n  for _ in range(m)]

    elapsed_max = 0
    for i, a in enumerate(M0):
        for j in range(n):
            b = [m1[j] for m1 in M1]
            sum_of_product = sum([ai*bi for ai, bi in zip(a,b)])
            # O[i,k] = sum(M0[i,:] * M1[:, k])
            O[i][j] = sum_of_product
    return O

# when `mat_power(M, 2**23)`, it took upto 1.8 sec 
# for multiplying two numbers during calculation
def mat_power(M, i):
    def _power(memo, i):
        if i in memo: return memo[i]
        m_sqrt = _power(memo, i//2)
        m = matmul(m_sqrt, m_sqrt)
        if i%2 != 0:
            m = matmul(m, M)
        memo[i] = m
        return m
    
    memo = { 0: identity(M),  # by definition, M**0 = I
             1: M}            # by definition, M**1 = M
    ans = _power(memo, i)
    #print (f'mat_power({i})[0][0]: {ans[0][0]}')  
    return ans
    
def identity(M):
    m, n = len(M), len(M[0])
    ans = [[0]*n for _ in range(m)]
    for i in range(m):
        ans[i][i] = 1
    return ans

mat_power 테스트 using matmul

M = [[1,1],
     [1,0]]
assert mat_power(M, 0) == [[1,0], [0,1]],   "0. M**0 by definition"
assert mat_power(M, 1) == M,                "0. M**1 by definition"
assert mat_power(M, 2) == [[2,1], [1,1]],   "0. M**2 correct answer"
assert mat_power(M, 2) == matmul(M, M),    "0. M**2 == M x M by definition"
assert mat_power(M, 3) == matmul(mat_power(M, 2), M), "1. M**3 == M**2 x M**1"
assert mat_power(M, 4) == matmul(mat_power(M, 2), mat_power(M, 2)), "1. M**4 == (M**2)**2 == M**2 x M**2"