[알고리즘] 동적계획법 (Dynamic Programming, DP)

Y_Sevin·2021년 12월 1일

Algorithm

목록 보기

1/2

동적계획법이란?

쉽게 말해 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말입니다.

동적계획법 특징

큰 문제를 작은 문제 단위로 나누어 풀때 작은 문제들이 반복이 일어나지 않도록 한번만 푸는 특징을 가지고 있습니다. 다음과 같은 특징을 가지기 위해 작은 문제의 정답을 구하면 어딘가에 저장해놓고 그보다 큰문제를 풀어갈때 똑같은 작은문제가 나타나면 앞서 저장한 작은 문제의 결과값을 이용합니다.

📝메모이제이션(Memoization)

앞서 말했듯 동적계획법은 똑같은 작은 문제들이 반복될때 작은 문제의 계산된 결과를 저장하고 이를 활용하여 중복 계산을 줄입니다. 이것을 Memoization 이라 부릅니다.

재귀함수와 동적계획법

재귀함수 형태의 피보나치 수열

def fibo(x):
    if x <= 2:
        return 1
    return fibo(x-1) + fibo(x-2)

fibo(6)의 실행과정

실행과정을 보면 이미 진행됐던 연산인데도 불구하고 fibo(4)의 연산은 두 번, fibo(3)의 연산은 세 번 진행되는 등 중복연산이 발생하는 것을 볼 수 있습니다.

숫자가 작을 때는 이러한 연산이 괜찮지만, 숫자가 조금만 커진다면 시간 복잡도와 공간 복잡도가 지수 스케일로 증가하는 문제점이 있습니다.

✨동적 계획법✨

동적 계획법에서는 이러한 반복계산을 막기 위해 이전에 연산했던 값들을 저장하고 이미 한번 진행한 연산이 필요한 경우 연산 진행하는것이 아니라 저장한 값을 가져옵니다.

동적 계획법으로 구하는 피보나치 수열

 def fibo(x):
    if x <= 2:
        return 1
    if mem[x] != 0:
        return d[x]
    mem[x] = fibo(x-1) + fibo(x-2)
    return d[x]

x가 2 이하일 경우 1을 반환하고, 그 이상일 경우 mem[x]에 저장된 연산 값이 없는지 검사합니다. 없을 경우, 연산을 통해 mem[x]에 값을 저장하고, 반환합니다. 만약 저장된 연산 값이 존재한다면 바로 mem[x]을 반환하게 됩니다.

TOP-DOWN
위에서 아래로 내려오는 방식, 메모이제이션 사용
즉, 큰 문제부터 시작해서 계속 작은 문제로 분할해 가면서 푸는 것을 말합니다.

fibonacci(4)를 구하는 큰 문제는 fibonacci(3)과 fibonacci(2)를 구하는 작은 문제로 나눌 수 있습니다.

def fibo(int n):
  if (n<=2):
    return 1
  if (mem[n]==0):
    mem[n] = fibo(n-1) + fibo(n-2)
  return mem[n]

BOTTOM-UP
TOP-DOWN 방식과 다르게 문제 풀이가 아래에서 위로 진행되는 방식, DP 테이블
즉, 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것을 말합니다.

def fibo(int n):
  fiboData[0] = 0
  fiboData[1] = 1
  for (int i=2; i<=n; i++):
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2]
  return fiboData[n]