Dynamic Programming, DP

큰 문제를 작은 문제로 나누어 푸는 것

다이나믹 프로그래밍(동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장해 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌, 하나의 문제해결 패러다임으로 볼 수 있음

Q.분할정복과 비슷하다?
A. 비슷하지만 작은 문제가 중복이 일어나는지, 안일어나는지에 대한 차이가 있다.
분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이다. 작은 문제에서 반복이 일어나는 부분이 없다
DP는 작은 문제들이 반복되는 것(답이 바뀌지 않음)을 이용해 풀어나간다.

재귀방식과 다른점은 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용하여 매우 효율적으로 문제 해결이 가능하다.

시간 복잡도는 O(n^2) => O(f(n))로 개선 (문제에 따라서 다르다)
 

DP의 조건

• 작은 문제가 반복이 일어나는 경우
• 같은 문제는 구할 때마다 정답이 같음
  
  예를들어 피보나치 수열의 경우, fn = fn-1 + fn-2라는 수식을 가진다.
  즉, n이 어떤 수이건 n-1번째 수와 n-2번째 수를 더해야 한다.
  하지만 병합정렬의 경우 수행시 작은 하위 문제로 쪼개지만 중복하여 하위 문제가 발생하지 않는다.
  분할된 부분 부분은 모두 독립적이고, 동일한 부분을 중복하지 않는다.

DP 사용하기

1) DP로 풀 수 있는 문제인지 확인
2) 문제의 변수 파악
3) 변수 간 관계식 만들기(점화식)
4) memoization or tabulation : 메모하기
5) 기저 상태 파악하기
6) 구현하기
 
1) DP로 풀 수 있는 문제인지 확인
보통 특정데이터 내 최대화/최소화를 계산하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.
 
2) 문제의 변수 파악
DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용한다.
=> 문제 내 변수의 개수를 알아내야 한다 => state 결정

피보나치 수열에선 n번째 숫자를 구하는 것이기에 n이 변수이다.
문자열 간의 차이를 구할 때는 문자열의 길이, Edit 거리 등 2가지 변수를 사용
Knapsack 문제에서는 index, 무게로 2가지의 변수를 사용한다.
 

3) 변수 간 관계식 만들기(점화식)
변수들에 의해 결과 값이 달라지지만 동일한 변수인 경우 결과는 동일하다.
또한 우리는 그 결과값을 그대로 이용할 것 이므로 그 관계식을 만들어낼 수 있어야 한다.
그런 식은 점화식이라고 부르고, 이를 통해 짧은 코드 내 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다.

  
4) memoization or tabulation : 메모하기
변수의 값에 따른 결과를 저장해야 한다.
변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.

  
5) 기저 상태 파악하기
가장 작은 문제의 상태를 알아야한다.
피보나치 수열을 예로 들자면 f(0) = 0, f(1) = 1과 같은 방식이다. 이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 2개로 볼 수 있다.

  
6) 구현하기
2가지 방식이 있다 :

• Top-Down : Memoization 방식, 재귀 사용
• Bottom-Up : Tabulation 방식, 반복문 사용

Top-Down

def fibonacci_top_down(n):
    if memo[n] > 0:
        return memo[n]
​
    if n <= 1:
        memo[n] = n
        return memo[n]
​
    else:
        memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
        return memo[n]
    
if __name__ == '__main__':
    memo = [0 for i in range (100)]
    n = int(sys.stdin.readline())
    print(fibonacci_top_down(n))    

큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결한다
위에서부터 바로 호출을 시작해 dp[0]까지 내려간 다음 결과 값을 재귀를 통해 전이시켜 재활용하는 방식.

소스의 가독성이 증가하나 작성이 어렵다.
 

Bottom-Up

def fibonacci_bottom_up(n):
    if n <= 1:
        return n
​
    fir = 0
    sec = 1
    for i in range(0, n-1):
        next = fir+sec
        fir = sec
        sec = next
    return next
    
if __name__ == '__main__':
    n = int(sys.stdin.readline())    
    print(fibonacci_bottom_up(n))

작은 문제부터 차근차근 구해나아가는 방법
풀기는 쉽지만 소스의 가독성이 저하할 수 있다.

참고자료 

https://galid1.tistory.com/507
https://hongjw1938.tistory.com/47