Dynamic Programming

  Dynamic Programming(동적 프로그래밍)은 구하고자 하는 최적해가 부분문제들로 이루어져있고 부분문제들이 또다른 작은 부분문제들로 이루어졌을 때 풀이시간 단축을 위해 사용된다. 반복되는 부분문제들을 한번씩만 계산하여 저장한 뒤, 저장한 값을 사용하여 중복되는 부분문제들의 계산을 줄이는 방법이다. 저장된 값을 재사용함에 따라 풀이시간은 감소하지만, 저장하는 값들의 공간만큼 메모리 공간이 더 소모된다는 단점이 있다.

 

DP 문제를 풀때의 일반적인 접근은 아래와 같다.

 

1. 최적해의 구조적 특징을 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 Bottom-Up으로 계산한다.

4. 계산된 정보들로부터 최적해를 구성한다.

 

정의만 읽어보면 두루뭉실하니, 예제를 보면서 이해해보자.

 

Problem : 피보나치 수열의 N번째 숫자를 구하라.

 

1. 피보나치 수열의 구조적 특징 : n번째 숫자는 n-1번째 숫자와 n-2번째 숫자를 더한 값이다.

 

피보나치 수열

2. 최적해의 값을 재귀적으로 정의한다.

def fib(n):
    if n==1 or n==2:
    	result = 1
    else:
    	result = fib(n-1) + fib(n-2)
    return result

  이 상태로도 풀이가 가능하지만, 시간초과 / Recursion Limit 초과로 불가능한 경우가 많다. 위의 코드대로 풀이를 진행하면, fib(5)를 구할 때 아래와 같이 반복된 계산을 수행하게 된다.

 

색깔별로 중복된 계산을 표시했다.

  따라서, 현재 구현된 재귀 방식의 시간복잡도는 O(2^n)이다. 계산 횟수를 줄이기 위해 계산값들을 memo라는 배열 안에 저장하고, 저장된 값들을 사용해보자.

def fib(n):

    memo = [0, 1, 1]
    memo.extend([0 for _ in range(n)])
    
    def find(n):
        if memo[n]:
            return memo[n]
        else:
            result = find(n-1) + find(n-2)
            memo[n] = result
        return result

    return find(n)

  우선 memo라는 배열을 만들어준 뒤, 계산한 값은 memo[n]에 저장한다. memo[n] 값이 존재하는 경우, 계산하지 않고 바로 이 값을 사용한다. 이렇게 중복되는 부분문제들의 결과값을 저장하여 사용하는 방법을 Memoization이라고 한다.

위와 같은 방식의 시간복잡도는 O(n)이 된다.

 

3. 최적해의 값을 Bottom-Up으로 계산한다.

  위와 같은 방법은 재귀적으로 호출하기 때문에 Max Recursive Limit에 걸리는 문제가 발생할 수 있다. 따라서 그냥 1부터 n까지 순차적으로 memo 배열을 채워가는 방식을 생각할 수 있는데, 이를 Bottom-up 방식이라고 한다. 재귀를 사용한 것보다 더 간단하고, 빠르다.

 

def fib(n):

    memo = [0, 1, 1]
    memo.extend([0 for _ in range(n)])
    
    for i in range(3, n+1):
        memo[i] = memo[i-1] + memo[i-2]

    return memo[n]

 

물론 피보나치보다 더 어려운 문제들을 접할 때는, 최적해의 구성을 통해 부분문제들을 정의하는 것이 매우 어려울 때가 많다. 추후 다른 문제들 Review를 통해 알아본다