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

한은기·2022년 2월 19일

Data Structure & Algorithm

목록 보기

7/10

1. 동적계획법

1-1. 개요

동적계획법(Dynamic Programming, DP)은, 처음 진행하는 연산은 기록을 하고, 이전에 했던 연산이면 기록한 값을 쓰거나 해당 연산은 넘어가는 방식이다. 하나의 문제를 여러 작은 문제로 나누며 이를 결합하여 최종 답을 구한다.

재귀(Recursion)을 사용했을 때 비효율적인 계산을 줄일 수 있다는 측면에서 동적계획법을 많이 사용한다. 예를 들어, 피보나치 수열을 재귀함수로 구현한다면 중복된 연산이 발생할 수 있다. 이를 동적계획법을 사용해 풀이한다면 중복 연산을 건너뛸 수 있다. 시간복잡도는 $O(n^2)$ 에서 $O(f(n))$ 으로 개선된다.

### 단순 재귀함수
def fibo(n):
    if n <= 2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
        
### 동적계획법
fibo_result = [0] * 100;
def fibo(n):
	if n <= 2:
        return 1
    if fibo_result[n] == 0:
        fibo_result = fibo(n-1) * fibo(n-2)
    return fibo_result[n];

분할 정복 알고리즘(Divide and Conquer)과는 '하위 문제로 쪼개 큰 문제를 해결한다'는 점에선 유사하나, 분할 정복 알고리즘의 경우 하위 문제가 중복해 연산이 일어나지 않는다는 차이점이 있다.

1-2. 메모이제이션

이미 진행했던 연산을 기록해두어 중복 계산을 줄인다고 했는데, 이를 메모이제이션(Memoization)이라고 한다. 예를 들어, 0부터 9까지 원소가 있을 때 10개의 배열을 False으로 초기화해 만들어놓고 1을 방문했다고 하면 1에 True 표기를 해두는 식이다. 추후에 다시 1을 탐색한다면 이곳에 True가 표시되어 있으므로 이 경우는 넘어가는 것이다. 또는 해당 원소에 특정 값을 넣고 다시 그 원소로 왔을 때는 다시 계산하기보단 저장한 값을 꺼내서 활용할 수도 있다.

2. 주의점

동적계획법을 사용하기 위한 조건에는 아래와 같은 두 가지가 있다.

[A] '겹치는 부분 문제(Overlapping Subproblems)'일 것
[B] '최적 부분 구조(OPtimal Substructure)'일 것

DP는 문제를 나눠서 값을 재활용하는 방식이므로 동일한 조건의 작은 문제들이 반복해 나타나야 하므로 [A] 조건이 필요하다.
또한 작은 문제의 최적 값이 큰 문제의 최적값에도 적용이 가능해야 한다. 작은 문제에서는 이 방법이 최적이었는데 큰 문제로 넘어가 더해줬을 때 최적이 아니라면 적용이 안된다. 일례로 X-Y-Z로 이어진 길이 있을 때 X-Y 길까지 오는 최단 거리와 Y-Z 길의 최단거리를 합했을 때가 X-Z 길의 최단거리가 되야 하는 것이다. 때문에 [B] 조건이 필요하다.

3. 구현 방식

동적계획법의 구현 방법에는 두 가지가 있다. 하나는 TOP-DOWN 방식이며, 다른 하나는 BOTTOM-UP 방식이다.

💎 Top-Down
최종 답인 DP[N]을 구하기 위해 위에서부터 호출을 시작하고 DP[0]까지 내려간 뒤, 해당 결과를 재귀로 전이시켜 재활용한다. 피보나치 수열을 구하는 예가 해당한다.

💎 Bottom-Up
Top-Down과는 반대로 아래에서 위로 올라가며 계산 결과를 누적시켜 큰 문제를 해결한다. 여기서는 메모이제이션을 'Tabulation'이라고 하는데, 사전적 정의로는 '도표 작성; 표, 목록'이다. 반복하며 DP[k](k는 0 이상 N 이하인 정수)를 채우는 과정을 'table filling'이라 하며, 테이블에 저장된 값을 직접 접근해 재활용하기 때문이다.

4. 예시 문제

4-1. 2 x n 타일링 (프로그래머스)

👉 문제 링크
🔍 풀이방식
처음에는 재귀함수를 호출해 팩토리얼을 직접 계산하는 문제로 풀이하였다. 그러나 런타임 에러가 발생해 실패했다. 이후 피보나치 수열을 DP로 푸는 방식을 적용해 성공했다.

가로 길이(n)이 1일 때는 세로로 긴 타일 한 개만 놓을 수 있어 그 값이 1이고, n=2일 때는 가로로 긴 타일을 두 개 놓거나 세로로 긴 타일을 두 개 놓을 수 있어 값이 2가 된다. n=3일 때는 '세로로 긴 타일 하나 & n=2일 때 경우의 수'와 '가로로 긴 타일 두 개 & n=1일 때 경우의 수'의 합으로 구할 수 있다. 점화식이 $dp[k] = dp[k-1] + dp[k-2]$ 꼴로 피보나치 수열과 모양이 같다.

경우의 수가 매우 많아 수의 크기가 크므로 매 연산마다 나머지 연산으로 업데이트 해주었다.

def solution(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        case = dp[i - 1] + dp[i - 2]
        dp[i] = case % 1000000007
    return dp[n]

4-2. 거스름 돈 (프로그래머스)

👉 문제 링크
🔍 풀이방식
0원을 만들 수 있는 경우의 수를 1개라고 하고 DP를 채워나간다. DP의 초깃값은 '가장 작은 단위의 동전'만 써서 만드는 경우의 수로 한다.
이후 '거스름돈'을 '가장 작은 단위의 동전' 단위로 값을 키워가며 '특정 단위의 동전'을 써서 거슬러줄 수 있는 경우의 수를 구한다.
예를 들어 20원을 거슬러주고 동전은 [2원, 5원, 7원, 15원]이 있다고 하자. 20원 = 2원 + 18원 = 5원 + 15원 = 7원 + 13원으로 나눌 수 있고 각각의 경우(18원, 15원..)에 다시 더 작은 동전으로 나눌 수 있다.
따라서 특정 액수를 거슬러 줄 수 있는 경우의 수는 '거슬러 줄 돈'에서 '탐색 중인 특정 단위의 동전'을 뺀 금액을 줄 수 있는 경우의 수인 것이다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> money) {
    vector<long long> dp(n + 1);
    dp[0] = 1;

    for (int i = money[0]; i <= n; i += money[0])
        dp[i] = 1;

    for (int i = 1; i < money.size(); i++)
    {
        for (int change = 0; change <= n; change++)
        {
            if (change >= money[i])
                dp[change] += dp[change - money[i]];
        }
    }

    return dp[n] % 1000000007;
}

참고자료

한은기

🏫Inha Univ. Naval Architecture and Ocean Engineering & Computer Engineering (Undergraduate) / 🚢Autonomous Vehicles, 💡Machine Learning