[Algorithm] Dynamic Programming

Dynamic Programming

동적 계획법(dynamic programming)이란 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 푸는 방법을 말한다.

DP 조건

• 큰 문제를 작은 문제들로 나눌 수 있을 때
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 적용할 수 있을 때
• 작은 문제들이 반복될 때

---

Fibonacci

F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2).

Recursive

# O(2^n)
def recur_fibo(n):
    if n == 0 or n == 1:
        return n
    else:
        return recur_fibo(n-1) + recur_fibo(n-2)

# 387 ms ± 7.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Top-Down

재귀적으로 구현하는 경우가 대부분 Top-Down
큰 문제를 해결하려고 할 때 아직 작은 문제가 해결되지 않았다면 작은 문제를 해결함

위에 그냥 재귀랑 차이점? memoization

memoizaion

한 번 계산한 작은 문제들의 답을 저장해놓고 사용

# O(n)
fibo_arr = [0, 1] # memoization
def topdown_fibo(n):
    if n < len(fibo_arr):
        return fibo_arr[n]
    else:
        fibo = topdown_fibo(n-1) + topdown_fibo(n-2)
        fibo_arr.append(fibo)
        return fibo

# 205 ns ± 12.9 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Bottom-Up

Top-Down과 반대로 작은문제부터 해결해나가서 큰 문제를 해결하는 방식

# O(n)
def bottomup_fibo(n):
    if n == 0 or n == 1:
        return n
    else:
        fibo_arr = [0, 1]
        for i in range(2, n+1):
            fibo_arr.append(fibo_arr[i-1] + fibo_arr[i-2])
        return fibo_arr[n]

# 6.12 µs ± 114 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

---

[BOJ] 9095번 1, 2, 3 더하기

# Bottom-Up

memo = [0, 1, 2, 4]

def cal(n):
    if n >= len(memo):
        for i in range(len(memo), n+1):
            memo.append(memo[i-1] + memo[i-2] + memo[i-3])
    print(memo[n])

[BOJ] 11726번 2xn 스타일링

# Bottom-Up)
# 1과 2로 n을 만드는 경우의 수 구하기
memo = [0, 1, 2]

def cal(num):
    if num >= len(memo):
        for i in range(len(memo), num+1):
            memo.append(memo[i-1] + memo[i-2])
    return memo[num]

---

References

https://www.baeldung.com/cs/fibonacci-top-down-vs-bottom-up-dynamic-programming

https://www.youtube.com/watch?v=eJC2oetXaNk

https://galid1.tistory.com/507