📘[DP] 동적 계획법(Dynamic Programming)이란?

동적 계획법(Dynamic Programming)이란?

동적 계획법은 큰 문제를 작은 문제로 나누어 푸는 문제를 말한다.
큰 문제를 작은 문제로 나누는 것은 분할 정복(Divide and Conquer)와 비슷해보인다. 하지만 결정적인 차이점이 있는데, 바로 작은 문제가 중복이 일어나는지 일어나지 않는지이다.

분할 정복은 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방식이다. 특징은 작은 문제에서 반복이 일어나지 않는다는 점이다.
동적 계획법은 작은 문제들이 반복되는 것이 특징이며, 이를 이용해 풀어나가는 방식이다.

동적 계획법 방법

동적 계획법으로 문제를 푸는 방법은 모든 작은 문제들을 한 번만 푸는 것이다.
정답을 구한 작은 문제들을 어딘가에 메모(Momoization)해놓았다가, 같은 상황이 발생하면 그 결과값을 사용한다.

동적 계획법의 조건?

동적 계획법을 사용하는 조건은 다음과 같다.

1. 작은 문제가 반복이 일어나는 경우
2. 같은 문제는 구할 때마다 정답이 같아야 함

이러한 조건을 만족하는 경우만 동적 계획법을 사용할 수 있다.

동적 계획법 요약 - 장점

1. 메모리를 사용해서 중복 연산을 줄임
2. 중복 연산을 줄여서 수행 속도를 개선함

예시 - 피보나치 수열

피보나치 수열은 F(n) = F(n-1) + F(n-2)의 점화식을 갖는 순열이다. 이 문제는 재귀 함수를 통해 해결할 수 있지만, n이 증가함에 따라 호출되는 함수의 수가 기하급수적으로 증가하기 때문에 일정 수 이상의 순열을 구하기 어렵다.

재귀함수 사용

def fub(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

이 문제를 동적 계획법(DP)를 사용해 접근해보자.

1. 작은 문제들이 반복된다.
   예를 들어 F(5) = F(4) + F(3), F(4) = F(3) - F(2) 인데, 여기서 F(3)이 반복되는 것을 볼 수 있다. 즉, 작은 문제가 반복되고 있다는 뜻이다.
   
   

2. 같은 문제는 구할 때마다 정답이 같다.
   피보나치 수열은 F(1)과 F(2)의 값은 모두 1로 고정되어 있다.
   즉, 3번째 수열은 언제나 결과값이 2이고, 4번째 수열은 2 + 1이므로 언제든 결과값이 같다.

피보나치 수열 DP

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

참고자료

https://galid1.tistory.com/507
https://www.youtube.com/watch?v=0bqfTzpWySY&t=423s