[알고리즘 코테] 동적 계획법

Dynamic Programming (동적 계획법)

큰 문제를 작은 문제로 나누어 결과를 저장하여 다시 큰 문제를 해결하는 방법

• DP를 사용하는 이유 : 일반적인 재귀를 사용하면 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있기에 이를 해결하려고 사용함.
• DP 문제를 푸는 방법  
  •  탑다운(Top-Down) : 하향식, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
  •  바텀업(Bottom-Up) : 상향식, 가장 작은 문제들부터 답을 구해가면서 전체 문제의 답을 찾는 방식으로 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있음.
• DP를 사용하는 문제
  • 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있는 경우
  • 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 하는 경우, 그러나 부분 문제가 중복되지 않는 경우에는 사용할 수 없음
• 분할 정복(Divide and Conquer)과 비교
  • 공통점 : 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 이어서 큰 문제를 해결함.
  • 차이점 : 하위 문제가 중복이 일어나지 않으면 분할 정복으로 해결하고, 중복이 일어나면 동적 프로그래밍으로 해결함.
• 메모이제이션(Memoization) : DP 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모한 후 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법
• 대표적인 DP 예제 : 피보나치 수열
  • 재귀함수로 구현할 수 있으나, n이 커질수록 수행 시간이 기하급수적으로 늘어나게 됨. 시간복잡도는 O(2^n) 
  • DP로 구현하면 시간복잡도는 O(n)
   

재귀함수의 경우, 모든 노드를 방문해야 함.

def fibonacci(n):
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

DP의 경우, 노란색으로 칠해져 있는 노드만 방문하면 됨.

 

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