DP(다이나믹 프로그래밍)

다이나믹 프로그래밍으로 특정 범위의 값을 구하기 위해 다른 범위의 값을 이용하여 효율적으로 값을 구하는 최적화 이론의 한 기술인 알고리즘 설계 기법을 말합니다..

다이나믹 프로그래밍은 구체적인 알고리즘이라기보다는 문제해결을 위한 방법을 말하고 있다 . 하나의 큰 문제를 과거의 구한 해를 활용하여 찾는 방식을 말합니다.. 답을 구하기 위해 했던 계산을 계속적으로 해야 하는 종류의 문제인 최적 부분 구조에서도 다이나믹 프로그래밍을 활용해서 사용할 수 있습니다. 

다이나믹 프로그래밍은 한국어로는 동적 계획법이라고도 합니다. 

 

구현

다이나믹 프로그래밍과 분할 정복 알고리즘

공통점

다이나믹 프로그래밍은 기본적으로 분할 정복 알고리즘과 접근 방식이 비슷합니다.

• 다이나믹 프로그래밍의 알고리즘은 주어진 문제를 부분문제로 나누면서 각 부분 문제의 답을 통해 해당 문제의 답을 산출하는 것이다.
• 분할정복알고리즘은 하나의 큰 문제를 용이하게 문제를 풀 수 있도록 조금씩 나눠가면서 푼 후 다시 합쳐서 해결하는 알고리즘입니다.

이처럼  다이나믹 알고리즘과 분할 정복 알고리즘은 큰 문제를 하나의 작은 문제들로 나눈 후 결과값을 이용하여 답을 산출한다는 공통점을 가지고 있습니다.

차이점

• 다이나믹 프로그래밍은 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하여 나눈 후 주어진 부분 문제의 값을 한 번만 계산하도록 저장해두는 메모리제이션 기법을 사용하여 중복되는 값의 해를  상위문제 해결 시 재활용하여 사용합니다. 
• 분할 정복 알고리즘은 원래의 문제를 부분 문제로 나누고 있어 부분 문제에 중복이 없어 메모이제이션 기법을 사용하지 않습니다. 

즉 다이나믹 프로그래밍은 최적 부분 구조와 같은 중복된 하위 문제들을 분할 정복으로 풀이기위한 문제해결 방법입니다.

메모리제이션이란?

DP를 구현하기위한 방법 중 하나로, 한 번 계산된결과를 메모리에 저장하는 기법을 말해 중복된 문제가 나오면 메모리에 저장한 값을 호출함으로써 시간을 줄일 수 있다. 또한 값을 저장하다는 점에서 캐싱이라고도 말한다.

 

 

재귀함수 형태의 피보나치 수열

재귀함수를 이용을한 피보나치 수열은 f(2)와 같이 이미 문제를 풀었던 문제도 계산을 다시 한다는 점에서 시간 복잡도가 엄청 커지게 된다.

DP로 피보나치 수열을 계산할 경우

메모리제이션을 활용하여 계산하기에 작은문제로 구한 문제가 중복이되면 이미 구한 값을 바로 사용함으로서 시간복잡도가 O(N)이 걸린다.

 

DP구현 방법

DP를 구현 방법으로는 탑다운과 바텀업 두 방법을 가지고 문제를 해결할 수 있다. 

1. 탑다운(Top-Down)

• 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
• 위에서 부터 아내로 내려간다고 하여 '하향식'이라고 한다.
• 재귀함수를 이용한다.
• 점화식을 이해하기 쉽다는 장점을 가지고 있다.

import java.util.*;

public class Main {

    // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
    public static long[] d = new long[100];

    // 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
    public static long fibo(int x) {
        // 종료 조건(1 혹은 2일 때 1을 반환)
        if (x == 1 || x == 2) {
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            return d[x];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

2. 바텀업(Bottom-Up)

• 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식
• 바텀업 방식은 '상향식'이라고도 한다.
• 반복문을 사용한다.
• 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.

// 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
        d[1] = 1; // DP 테이블
        d[2] = 1;
        int n = 50; // 50번째 피보나치 수를 계산

        // 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
        System.out.println(d[n]);

 

대표적인 문제

1. 피보나치 수열
   피보나치 수열은 다이나믹 프로그래밍의 대표적인 예시입니다. 피보나치 수열은 이전 두 항을 더하여 현재 항을 만들어가는 수열이며, 특정 위치의 피보나치 수를 계산하는 데에 다이나믹 프로그래밍을 활용할 수 있습니다. 중복 계산되는 부분 문제들을 메모이제이션(memoization)이나 바텀업(bottom-up) 방식으로 저장하면서 계산하면 시간 복잡도를 획기적으로 줄일 수 있습니다.
2. 배낭 문제 (Knapsack Problem)
   배낭 문제는 주어진 가방의 용량에 맞춰 물건들을 넣을 때, 어떤 물건들을 선택하여 가치의 합을 최대화하는 문제입니다. 다이나믹 프로그래밍을 이용하여 가능한 모든 물건의 조합을 검사하지 않고도 최적해를 찾을 수 있습니다.
3. 최장 공통 부분 수열 (Longest Common Subsequence, LCS)
   두 문자열이 주어졌을 때, 이들의 최장 공통 부분 수열을 찾는 문제입니다. 다이나믹 프로그래밍을 사용하면 각 문자열의 부분 문제들을 해결하여 최장 공통 부분 수열을 효율적으로 찾을 수 있습니다.
   
   
4. 최단 경로 문제 (Shortest Path Problem)
   그래프에서 두 정점 사이의 최단 경로를 찾는 문제입니다. 다익스트라 알고리즘과 플로이드-와샬 알고리즘이 다이나믹 프로그래밍 기법을 활용하여 최단 경로를 찾는 대표적인 예시입니다
5. 분할 가능 배낭 문제 (Fractional Knapsack Problem)
   이전에 언급한 배낭 문제와 비슷하지만, 물건을 쪼개서 담을 수 있는 경우를 다루는 문제입니다. 이 문제는 탐욕 알고리즘으로도 해결 가능하지만, 다이나믹 프로그래밍으로 접근할 수도 있습니다.

다이나믹 프로그래밍은  큰 규모의 문제를 효율적으로 해결할 수 있는 강력한 알고리즘 기법입니다. 그러나 적용에 있어서는 문제의 구조를 잘 파악하고, 중복 계산을 피할 수 있도록 설계하는 것이 중요합니다.