[DP]note 5

동적 프로그래밍

ex. 피보나치

재귀적으로 구현할 경우 중복 호출로 인한 심각한 비효율

// 피보나치 - 재귀 호출
int fib(int n)
{
	if (n == 1 || n == 2)
    	return 1;
	else 
    	return fib(n-1) + fib(n-2);
}

 

메모이제이션 방식: 중간 계산 결과를 caching 함으로써 중복 계산을 피함

// 피보나치 - 메모이제이션
int fib(int n)
{
	if (n == 1 || n == 2)
    	return 1;
    else if (f[n] > -1) // 배열 f가 -1로 초기화되어있다고 가정
    	return f[n]; // <- 이미 계산된 값이다.
	else {
    	f[n] = fib(n-2) + fib(n-1); // 중간 계산 결과를 caching
        return f[n];
	}
}

 

동적 프로그래밍: bottom-up 방식으로 중복 계산을 피함

// 피보나치 - 동적 프로그래밍
int fib(int n)
{
	f[1] = f[2] = 1;
    for

DP과 재귀적 호출의 차이점은 무엇일까

하향식(Top-down) vs 상향식(Bottom-up) 접근
재귀적 호출은 주로 하향식(top-down) 접근 방식을 사용합니다. 즉, 큰 문제를 작은 하위 문제로 나누어 해결하는 방식입니다.
동적 계획법은 주로 상향식(bottom-up) 접근 방식을 사용합니다. 작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 해를 구해나갑니다.

 

메모이제이션(Memoization)
동적 계획법은 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용합니다. 이를 통해 이전에 계산한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용합니다. 이는 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킵니다.

DP로 문제 푸는 방법

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

 

🧮 변수 간 관계식(점화식) 만들기
예를 들어 피보나치 수열의 f(n) = f(n-1) + f(n-2) 라는 식

 

DP 문제 해결 방식

1. Bottom-Up (Tabulation 방식) - 반복문 사용
Bottom-Up 방식은 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식입니다. 이를 위해 반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 결과를 배열 등에 저장합니다.

👍 일반적으로 더 직관적이고 이해하기 쉽습니다. 또한, 모든 작은 부분 문제를 해결하므로 최적 부분 구조를 보장합니다.

 

2. Top-Down (Memoization 방식) - 재귀 사용
큰 문제를 작은 부분 문제로 나누어 해결하는 방식입니다. 이를 위해 재귀 함수를 사용하여 문제를 작은 부분 문제들로 쪼개고, 중복 계산을 피하기 위해 이전에 계산한 값을 저장하는 Memoization을 활용합니다. Memoization은 캐싱을 통해 이전 계산 결과를 저장하여 중복 계산을 피하는 것을 의미합니다.

👍 Memoization은 재귀를 사용하므로 구현이 더 간단할 수 있습니다. 또한, 필요한 부분 문제만 해결하므로 계산 시간을 절약할 수 있습니다. 하지만 재귀 호출의 오버헤드가 발생할 수 있으며, 모든 작은 부분 문제를 해결하지 않을 경우 최적 부분 구조를 보장하지 않을 수 있습니다

대표적인 DP 문제들

행렬 경로 문제 

방문한 칸에 있는 정수들의 합이 최소화

for i ← 0 to n 
	maxSum[i, 0] ← 0; 
for j ← 1 to n 
	maxSum[0, j] ← 0; 
    
for i ← 1 to n                      
	for j ← 1 to n                                        
		maxSum[i, j] ← m[i, j] + max(maxSum[i-1,  j], maxSum[i,  j-1]); 

print(maxSum[n, n]);
# Θ(n^2)

 

DP는 다양한 문제에서 사용될 수 있습니다. 위의 2가지 조건을 참고하여 DP로 해결할 수 있는 문제인지 파악할 수 있습니다. 보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많습니다.

 

피보나치 수열 > Top-Down 방식

피보나치 수열은 이전 두 항의 합으로 이루어지는 수열입니다. 동적 계획법을 사용하여 피보나치 수열을 구할 수 있습니다. 작은 문제부터 시작하여 계산 결과를 저장하고 이를 이용하여 큰 문제의 해를 구합니다.

 

최장 증가 부분 수열(Longest Increasing Subsequence) > Bottom-Up 방식

만약 recursive 하게 푼다면? -> 엄청난 중복 호출 발생

int LCS(char* X, char* Y, int m, int n) {
▷ 두 문자열 X (길이 m)과 Y (길이 n) 의 LCS 길이 구하기
    if (m == 0 || n == 0)
        return 0;
    else if (X[m-1] == Y[n-1])
        return LCS(X, Y, m-1, n-1) + 1;
    else
        return max(LCS(X, Y, m-1, n), LCS(X, Y, m, n-1));
}

 

DP 풀이

int lcs(int m, int n) { /* m: length of X, n: length of Y */
    int[][] c = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++)
        c[i][0] = 0;

    for (int j = 0; j <= n; j++)
        c[0][j] = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1])
                c[i][j] = c[i - 1][j - 1] + 1;
            else
                c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
        }
    }

    return c[m][n];
}

시간복잡도: Θ(mn)

 

DFS로 풀면 너무 오래걸림 ->DP를 사용하자.

트리를 삼각형으로 변경하면 표처럼 된다. (아래 혹은 위로만 갈 수 있다.)

두 개의 삼각형 표를 만든다. DP 삼형 표에서는 최댓값을 저장해두는 표. 각 표에서는 ↓↘ 방향으로만 더하기가 가능.

마지막 줄을 통해 찾는 값의 답이 30임을 알 수 있다.

메모리를 사용한다 -> 배열 혹은 자료구조를 만든다.

중복 연산을 줄인다 -> 연산한 결과를 배열에 담아 같은 연산을 다시 하지 않는다.

왜 DP 인가? DP보다는 기억하며 풀기 기억하기 알고리즘이 더 직관적인 번역인거 같다.

이 문제가 DP인지 판단하는 기준

1. DFS/BFS로 풀 수 있지만 경우의 수가 너무 많은 문제. 정수 삼각형이 500줄이라면? - 일단 패턴 파악하기. 이거 각이 안나오는데? 싶으면 DP로 풀기

2. 경우의 수들에 중복적인 연산이 많은 경우 - 이 중 가장 좋은 조합을 찾는 것 방법으로 나아가기

3. 문제 해결 접근 방법 - DP는 30분동안 봐도 답이 안나오면 식을 보고 풀이해보는 것이 좋다.

어떤 정보를 담아야 뒤 단계로 안갈까 - 최적의 답을 쌓아가자! 가 DP 식 사고방식