동적계획법(DP, Dynamic Programming)

NAMYUSEONG·2022년 3월 25일
0

계단오르기 문제를 재귀함수를 이용해서 풀려고 하다가 동적계획법에 대해 알게되어 관련 내용을 정리해본다

동적계획법이란?

  • 복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 방법
  • 부분 문제 반복(Overlapping subproblems)와 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 짧은 시간 안에 풀 때 사용

이해하기 쉬운 예시로 피보나치 수열에 대해 살펴보자


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

수학적인 정의로 볼때, 매우 간단하고 명료하게 표현할 수있지만,
컴퓨터가 계산하기에는 부적합하다고 한다.

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1

파이썬에서는 재귀함수를 이용해 간단하게 함수를 만들어볼 수 있다.

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

n이 작은 값일 때는 괜찮지만, n이 조금만 커져도 시간복잡도와 공간복잡도가 기하급수적으로 증가하게 된다. n = 35쯤 입력하면 멍하게 있는 자신을 보게 된다.

동적 계획법 형태의 피보나치 수열

동적계획법에서는 반복되는 계산을 막기 위해 이전에 계산했던 내용을 배열에 저장한다.
대표적으로는 top-down과 bottom-up이 있다고 한다.

Top-down

메모이제이션(memoization)을 이용한 재귀함수 방식

큰 문제부터 시작해서 작은 문제로 분할해가면서 풀 수 있는데, 계산된 값들을 메모리에 저장해서 다시 계산하지 않아도 된다.

def fib_2(n):
  d = [0]*(n+1)
  def fib(n):
    if n == 1 or n == 2:
      return 1
    if d[n] != 0:
      return d[n]
    d[n] = fib(n-1) + fib(n-2)
    return d[n]
  return fib(n)

Bottom-up

최초 값부터 차례대로 계산해 table에 저장하는 타뷸레이션(Tabulation)방식

시작부분은 f(0), f(1)부터 시작해 더해가면서 최종적으로 f(n)에 도달한다.

def fib_3(n):
  F = [0 , 1]
  for i in range(2, n+1):
    F.append(F[-1] + F[-2])
  return F[-1]

계단오르기 문제

최대 한 번에 m개의 계단을 올라갈 수 있을때, n개의 계단을 올라가는 방법의 수는?

점화식을 생각해보면 마지막에 한 번에 얼마의 계단을 올라가느냐를 고민해보면 된다.
최대 m 계단을 올라갈 수 있다면,
마지막에 1계단 + 마지막에 2계단 + ... + 마지막에 m계단 올라간 경우
f(n, m) = f(n-1, m) + f(n-2, m) + ... + f(n-m+1, m) + f(n-m, m)

초기 조건

  • 최대 올라갈 수 있는 계단수가 1이라면 가능한 경우의 수 => 1가지
  • n < m 일 경우 f(n, m) = f(n, n)
  • n == m 일 경우, f(n, n) = f(n-1, n-1) * 2
    a) 1 계단을 먼저 올라가고, m-1 계단을 올라가는 경우의 수
    b) m-1 계단을 먼저 올라가고, 1계단을 올라가는 경우의 수
    c) m계단을 한 번에 올라가는 경우의 수
    이때, 1과 2에서 1계단 씩 만으로 올라가는 경우가 겹치므로
    f(n, n) = f(n-1) + f(n-1) - 1 + 1

결과적으로 값이 도출 되려면 f(n-1, m) ~ f(n-m, m)까지의 값이 보장되어야 하므로,
n <= m 인 값들에 초기 값을 부여해 주어야 하는 것 같다

def clmb(n, m):
  memo = [[0] * (m+1) for _ in range(n+1)]
  def clmb_recur(n,m):
    if n < 1 or m < 1:
      return 0
    elif m == 1:
      return 1
    elif n == m:
      return 2 * clmb_recur(n-1, n-1)
    elif n < m:
      return clmb_recur(n, n)
    for i in range(1, m+1):
      memo[n][m] += clmb_recur(n-i, m)
    return memo[n][m]
  return clmb_recur(n, m)
profile
Divide and Conquer

0개의 댓글