DP(동적 계획법)

DP란?

동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 

이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 

일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

부분 문제 반복

부분 문제 반복이란 어떤 문제가 여러개의 부분 문제로 쪼개질 수 있는 경우를 말한다.

계속해서 같은 부분 문제가 여러번 재사용 되거나 재귀 알고리즘을 통해 해결되는 문제이다.

ex) 피보나치 수열에서 fib(n)문제는 fib(n-1)구하기와 fib(n-2)구하기의 부분문제로 쪼개질 수 있다.

 

최적 부분 구조

작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다.

ex) 피보나치 수열에서 fib(n)문제의 최적 답은 fib(n-1)구하기와 fib(n-2)구하기의 최적답으로 구할 수 있다.

 

메모이제이션

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때,

이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여

프로그램 실행 속도를 빠르게 하는 기술이다.

 

예시

https://school.programmers.co.kr/learn/courses/30/lessons/12900

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

    return dp[n-1] % 1000000007

 

1. dp = [0 for i in range(n)]로 미리 배열을 선언하는게 더 빠르다.

Good

dp = [0 for i in range(n)]

Bad -> list가 일정 길이를 초과할 때 마다 재선언을 해줘야 해서 효율성이 떨어진다.

l = [0, 1, 2]
for i in range(3, n):
    l.append(l[i-1] + l[i-2])

 

2. dp의 range를 n으로 제한하는 편이 좋다.

Good

dp = [0 for i in range(n)]

Bad -> 불필요하게 소모하는 메모리의 양이 많다(공간 복잡도)

dp = [0 for i in range(60000)]

 

3. 모듈러 연산으로 입력되는 값의 크기를 줄여준다.

Good

for i in range(2, n):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

return dp[n - 1]

Bad -> CPU와 메모리가 더 큰 데이터 구조를 처리해야 하기 때문에 배열에 매번 큰 값을 저장하는 것이 더 느리다.

for i in range(2, n):
    dp[i] = (dp[i - 1] + dp[i - 2]) 

return dp[n - 1] % 1000000007

 

 

모듈러 연산:

https://developer-mac.tistory.com/84

모듈러 연산 (Modular arithmetic)

모듈러 연산의 증명:

https://sexycoder.tistory.com/66

모듈러 연산의 성질과 증명