동적 계획법

froajnzd·2024년 2월 2일

algorithm

목록 보기

8/11

DP (Dynamic Programming = 동적계획법)
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 기본적인 아이디어를 가지고 푸는 하나의 문제 해결 패러다임이다.
DP의 특징

시간복잡도
$O(f(N))$
: $f(N)$ 은 다항식 수준으로, 문제에 따라 다르다.

📕 DP를 사용해야하는 문제의 조건

아래 두 가지 조건을 모두 만족해야 한다.

1. Overlapping Subproblems(겹치는 부분 문제)

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

2. Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다!

만약, A-B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A-X / X-B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A-X-B가 정답이 된다.

💡 DP의 장점

중복 계산을 줄일 수 있다.
효율적인 시간 복잡도를 가질 수 있다.

🥺 DP의 단점

메모리 사용량이 크다. 중간 결과를 저장하기 위해 추가적인 메모리를 사용하기에, 문제의 크기가 커질수록 필요한 메모리도 증가할 수 있다.

📝 DP를 사용하는 문제의 예

피보나치 수열 > Top-Down 방식
배낭 문제(Knapsack Problem) > Bottom-Up 방식
최장 증가 부분 수열(Longest Increasing Subsequence) > Bottom-Up 방식
최단 경로 문제(Shortest Path Problem) > Bottom-Up 방식
문자열 편집 거리 문제(Edit Distance Problem) > Bottom-Up 방식

🎁 구현 방법

구현 전 과정

DP로 풀 수 있는 문제인지 확인한다.
문제의 변수 파악
변수 간 관계식 만들기(점화식)
메모하기(memoization or tabulation)
기저 상태 파악하기
구현하기

구현 방식

Bottom-Up (Tabulation 방식) - 반복문 사용
아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식

dp[0]가 기저 상태이고 dp[n]을 목표 상태
dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용한다
Top-Down (Memoization 방식) - 재귀 사용
dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식

cf. 분할 정복과의 차이점?

분할 정복과 DP는 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.

차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 DP를 쓴다는 것이다.

🏃‍ 예시 문제 1

<BAEKJOON: 실버 3> 1로 만들기

해답

숫자 N부터 TOP-DOWN 방식으로 3가지 방식 중 가능한 수를 queue에 추가하는 방식으로 접근하였다.

import sys
input = sys.stdin.readline
N = int(input())
dp = [0 for i in range(N+1)]
queue = []
queue.append((N, 0))

while queue:
    num, cnt = queue.pop(0)

    if num == 1:
        print(cnt)
        exit(0)

    if num % 3 == 0 and dp[num//3] == 0:
        queue.append((num//3, cnt+1))
        dp[num//3] = cnt+1
    if num % 2 == 0 and dp[num//2] == 0:
        queue.append((num//2, cnt+1))
        dp[num//2] = cnt+1
    if dp[num-1] == 0 and num - 1 > 0:
        queue.append((num-1, cnt+1))
        dp[num-1] = cnt+1

🏃‍ 예시 문제 2

<BAEKJOON: 실버 1> 쉬운 계단 수

해답

import sys
DIVIDE = 1000000000
N = int(sys.stdin.readline())
dp = [[0] * 10 for i in range(N+1)]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, N+1):
    dp[i][0] = dp[i-1][1]
    dp[i][9] = dp[i-1][8]
    for j in range(1, 9):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print(sum(dp[N]) % DIVIDE)

🏃‍ 예시 문제 3

<BAEKJOON: 골드 5> 동전

해답

https://d-cron.tistory.com/23 이 글을 보면 이해가 잘 될 것.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    coin = list(map(int, input().split()))
    M = int(input())

    dp = [0] * (M+1) # i원을 만들 수 있는 경우의 수
    dp[0] = 1
    # 각 동전마다 만들 수 있는 경우를 찾는다
    for c in coin:
        for i in range(0, M+1):
            # i번째 돈을 만드는 경우는 dp[i-동전단위]와 같다.
            if i >= c:
                dp[i] += dp[i-c]
    print(dp[M])