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

Dynamic Programming (동적 계획법)이란?

기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것입니다.

 

 

DP는 왜 사용하는 걸까?

피보나치 수열을 예시로 들 수 있습니다. 피보나치 수열은 아래와 같습니다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... => fibo(n) = fibo(n-1) + fibo(n-2)

이런 알고리즘에서 f(n)을 호출한다고 하면 아래와 같이 중복되는 숫자들이 늘어나게 됩니다. 

즉, 시간복잡도가 O(2^n)이 걸리게 됩니다. 하지만 이미 계산했던 값들을 저장한다면 O(n)까지 줄일 수 있습니다. 이것이 DP를 사용하는 이유입니다.

 

DP의 접근방식

기본적으로 분할 정복 알고리즘과 비슷합니다. 위에서의 트리구조처럼 각 부분으로 나누어서 문제의 답을 계산하고, 계산된 값을 통해 원래 문제의 답을 산출하기 때문입니다. 여기서 분할 정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있습니다. 동적 계획법의 경우 주어진 문제를 나눌 때 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 문제를 이용할 때에 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킵니다.

나무위키 출처

 

DP는 언제 적용하면 좋을까?

DP가 적용되기 좋은 경우는 2가지가 있습니다.

 

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

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

 

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

피보나치 수열에서 중복되는 계산들이 존재하는데, 저 계산된 값들을 저장하면 재활용할 수 있습니다.

 

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

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

만약, A-B까지의 가장 짧은 경로를 찾아가고자 할 때, 이전 케이스들의 결과값을 기반으로 최적의 결과를 찾는 방식입니다.

백준 2579 - 계단오르기 문제를 예시를 들자면 이전에 어떤 계단을 밟았고 그 때의 최적의 점수를 기반으로 다음 계단을 밟는 형식으로 진행됩니다. 

 

DP 적용 단계

1. DP로 풀 수 있는 문제인지 확인

위에서 설명드린 2가지 조건에 부합하는지 먼저 판단합니다.

 

2. 문제의 변수 파악

1번 조건과 관련하여 어떤 것들이 문제인지, 어떤 변수가 영향을 주는지 파악하는 단계입니다.

 

예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 됩니다. 

또, 유명한 Knapsack 문제에서는 index, 무게로 2가지의 변수를 사용합니다. 

 

3. 변수 간 관계식 만들기 (점화식)

변수들이 어떤 규칙에 따라 이런 결과를 만들고 있는지 파악하고 이것을 점화식으로 만들어야 합니다. 점화식이란 피보나치 수열의 규칙인 f(n) = f(n-1) + f(n-2) 처럼 규칙을 가지는 형태를 뜻합니다. 

점화식이 필요없는 DP도 존재할 수 있습니다. 백준 문제 유형에서 계산된 값들을 저장하는 것을 요구하는 문제들도 DP라고 표현하기도 합니다!

 

4. 계산된 값들 저장하기 - 메모리제이션 (Memorization)

변수의 값에 따른 결과를 저장하는 단계이며 이를 메모리제이션(Memorization)이라고 칭합니다.

변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나갑니다.

이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다. ex) 기본적인 배낭문제의 경우 2차원 배열을 만들어서 해결합니다.

 

5. 가장 작은 문제의 상태 파악하기

피보나치 수열을 예시로 f(0) = 0, f(1) = 1 과 같은 핵심 포인트를 찾아야 합니다. 이것이 존재해야지만 점화식을 통한 재귀문이 종료가 가능합니다.

 

6. 구현하기

DP의 구현 방식은 총 2가지가 존재합니다.

 

1) Bottom-Up 방식 (Tabulation) - 반복문 사용

아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식입니다.

dp[0]를 가장 작은 상태로 놓고 목표 상태인 dp[n]까지 계산해나가는 방식입니다. - 계단오르기 문제

 

왜 Tabulation 방식이라고 부르는가?

반복문을 통해 dp[0]부터 하나 하나 채우는 과정을 "table-filling"이라고 하며, 이 Table에 저장된 값에 직접 접근하며 재활용하므로 Tabulation이라는 명칭이 붙었습니다.

// Bottom-Up 구현
public int fiboTopDown(int n) {
	int[] dp = new int[n+1];
    dp[0] = 0; dp[1] = 1;
    
    for (int i=2; i<=n; i++) {
    	dp[i] = dp[i-1] + dp[i-2]; //Tabulation - table-filling
    }
    
    System.out.println(dp[n]);
}

2) Top-Down 방식 (Memorization) - 재귀 사용

dp[n]의 값을 찾기 위해 위에서부터 시작하여 dp[0]의 상태까지 내려간다음 해당 결과들을 전이시켜 dp[n]의 값을 찾는 방식입니다. 피보나치의 경우 f(n)에서 f(1) 또는 f(0)까지 내려가서 값을 얻은 다음 이 값들을 통해 상위 계산된 값들의 결과를 얻을 수 있습니다. 이러한 과정을 Memorization이라고 부릅니다.

 

각 방식의 예시 - 피보나치 수열을 기준으로 값이 Integer범위라고 가정하고 함수를 구현했습니다.

// Top-Down 구현
int[] dp;

public void fiboBottomUp(int n) {
	dp = new int[n];
	System.out.println(fibo(n));
}

public int fibo(int n) {
	if (n == 0) return 0;
    if (n == 1) return 1;
    if (dp[n] != 0) return dp[n];
    dp[n] = fibo(n-1) + fibo(n-2);
    return dp[n];
}

 

<참고>

https://hongjw1938.tistory.com/47

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95