동적계획법(Dynamic Programming)

🦄 다이나믹 프로그래밍

문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다. 메모리 공간을 약간 더 사용하여 시간을 획기적으로 줄일 수 있는 방법이다.

다이나믹 프로그래밍은 다음과 같은 조건을 만족할때 사용할 수 있다.

1. 중복된 하위 문제(Overlapping Subproblems)
   큰 문제를 작은 문제로 나눌 수 있다.
2. 최적 부분 구조(Optimal Substructure)
   작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

다이나믹 프로그래밍의 장단점

• 장점
  . 필요한 모든 가능성을 고려해서 구현하므로 항상 최적의 결과를 얻을 수 있다.
  . 메모리에 저장된 값을 사용하므로 큰 문제를 빠른 속도로 해결하여 최적의 해를 찾아낼 수 있다.
• 단점
  . 모든 가능성에 대한 고려가 불충분할 경우 최적의 결과를 보장할 수 없다.
  . 다른 방법론에 비해 많은 메모리 공간을 요구한다.

💻 피보나치

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시가 바로 피보나치 수열이다.
피보나치 수열은 현재 항을 계산하기 위해 이전 두항의 합을 구해야 한다.

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

💻 상향식(Bottom-Up)

더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다. 즉, 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식입니다. 데이터를 테이블 형태로 만들면서 문제를 풀이한다고 하여 타뷸레이션(Tabulation)방식이라고 부른다. 일반적으로 이 방식만을 다이나믹 프로그래밍으로 지칭하기도 한다. 바텀업 방식은 반복문을 이용하여 구현한다.

def fib(n)
    dp[0] = 0
    dp[1] = 1

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

💻 하향식(Top-Down)

하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스럽게 재귀로 풀어나간다. 즉, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식입니다. 기존 재귀 풀이와 거의 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 효율적인 방식으로, 메모이제이션(Memoization) 방식이라고 부른다. 탑다운 방식은 재귀 함수 깊이와 관련된 오류가 걸릴 수 있고 재귀 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있기 때문에 반복문을 활용하는 바텀업 방식으로 다이나믹 프로그래밍 방법으로 해결하는 것이 권장된다.

def fib(n)
    if n <= 1:
        return n

    if dp[n]:
        return dp[n]
    dp[n] = fib(n-1) + fib(n-2)
    return dp[n]

 

메모제이션 이란?
다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다. 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다.

🕐 시간 복잡도

재귀구조 브루트 포스	바텀업	탑다운
O(2^N)	O(N)	O(N)