동적계획 알고리즘이란?

  • 크고 복잡한 문제를 나누어 작고 간단한 여러 문제로 푸는 방식
    • 분할 정복 알고리즘 : 간단한 문제가 될때 까지 문제를 나눈 다음 답을 도출하고 그 답들을 조합하여 원래 문제의 답을 도출
    • 최적 부분구조(Optimal Substructure) : 작은 문제의 최적 솔루션이 큰 문제의 최적 솔루션에 포함
  • 나누어진 문제를 풀다보면 재귀로 인한 중복된 하위 문제가 나타나 효율이 낮아지게 된다
  • DP테이블을 이용하여 이전에 계산했던 값을 저장해 재사용하여 계산횟수를 줄일 수 있다
    • 메모이제이션(Memoization) : 한번 계산한 결과를 메모리에 저장하여 다시 계산하지 않고 사용 (=캐싱)

DP테이블

  • 일반적으로 dp테이블의 크기인 O(n)의 시간복잡도를 갖지만 문제에 따라 종류가 m만큼 주어지면 O(nm)으로 나타난다
  • dp테이블 인덱스 i가 뒤쪽으로 갈수록 앞쪽의 결과를 포함하고 있기 때문에 인덱스 근처의 i-1, i-2만 참고해서 사용한다

DP테이블에 데이터를 채우는 방법

  1. 1차원 테이블
    1. 1번만 채우는 방법 : i-1이나 i-2를 참고하여 인덱스 i의 값을 채워 나간다 O(n)
    2. 계속해서 갱신시키는 방법 : 종류가 여러개(m) 일 경우 종류마다 dp테이블을 갱신시켜 나간다 O(nm)
      • 종류가 여러개 일때, 2차원 테이블로 만들지 않고 1차원 테이블에서 갱신시켜 처리할 수도 있다
  2. 2차원 테이블
    1. 상태를 함께 저장해야 하는 경우
      • 이전 단계에서 무엇인가 하지 않은 경우/한 경우 구분 : dp[i][0], dp[i][1]
      • 문제에서 주어진 데이터(ex 0-9)가 매번 인덱스(i)에 다르게 적용되는 경우 : dp[i][0]~dp[i][9]
    2. 구간 L~R에 대한 문제를 해결할 경우
      • L의 인덱스 i, R의 인덱스 j : dp[i][j]

    ● 문제에 따라 새로운 2차원 DP테이블을 만들지 않고 기존의 2차원 graph에서 값을 갱신시켜 나가는 것도 가능하다

문제

1. 피보나치 수열 [O(n)]

  • 재귀호출방식
def fib(n):
    if n <= 1: 
        return n
     else:
        return fib(n-1) + fib(n-2)

  • O(2n)

  • Top-Down 방식(메모이제이션)

    • 재귀를 사용하지만 dp테이블을 사용하여 이미 계산된 결과를 재사용한다
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(n)

  • ★Bottom-Up 방식(DP)

    • for문을 사용하여 하위부터 차례로 풀어나간다
n = int(input())
dp = [0] * (n+1)

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

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

     return dp[n]

print(fib(n))
  • O(n)

2. LIS(Longest Incresing Subsequence) - 최대 부분 증가수열 [O(n)]

  • 한 수열에서 가장 길게 증가하는 원소갯수
n = int(input())        # 8
nums = list(map(int, input().split()))    # 5 3 7 8 6 2 9 4
dp=[1]*n

for i in range(1, n):
    for j in range(i-1,-1,-1):
        if nums[i] > nums[j]:
            dp[i] = max(dp[j]+1, dp[i])
    
print(max(dp))    # 4

→ i는 dp테이블 만큼 돌고 j는 i-1부터 0까지 돈다

3. 동전 거스름돈(동전의 액면이 배수 관계가 아닐 경우) [O(nm)]

  • ex) 100, 80원
INF = 16

n = int(input())        # 3
coins = list(map(int, input().split()))     # 1 2 5
m = int(input())        # 15
dp = [INF] * (m+1)
dp[0]=0

for i in range(n):
    for j in range(coins[i], m+1):
        dp[j]=min(dp[j-coins[i]]+1, dp[j])
print(dp[m])

4. 0-1 배낭 문제(짐을 쪼갤 수 없는 경우) [O(nm)]

  • 갯수무한
n, c = map(int, input().split())        # 4 11
dp=[0]*(c+1)

for i in range(n):
    w, v = map(int, input().split())    # 5 12 / 3 8 / 6 14 / 4 8
    for j in range(w, c+1):
        dp[j]=max(dp[j-w]+v, dp[j])

print(dp[c])    # 28

5. 최대 점수 [O(nm)]

  • 갯수제한 (문제는 1번밖에 풀 수 없다)
  • 2차원 dp테이블을 사용하여 문제 종류마다 dp테이블을 만들어 중복해서 푸는 경우를 방지할 수 있다
  • 하지만, 메모리 절약을 위해 기존과 같이 1차원 dp테이블을 사용하게 만들 수 있다
    • dp테이블을 뒤에서부터 접근하여 중복을 해결할 수 있다
    • 1개의 dp테이블에 문제 종류(회전)마다 덮어씌운다고 생각
    • i를 기준으로 지나간 뒷 부분은 현재회전의 값, 지나가지 않은 앞 부분은 이전회전의 값
n, m = map(int, input().split())    # 5 20
dp = [0] * (m+1)

for _ in range(n):
    p, t = map(int, input().split())  # 10 5 / 25 12 / 15 8 / 6 3 / 7 4
    for i in range(m, t-1, -1):
        dp[i]=max(dp[i-t]+p, dp[i])
print(dp[m])