[TIL] 동적 계획법(DP: Dynamic Programming)에 대해

오늘도 백준에서 문제를 풀던 도중, “동적 계획법” 개념이 필요한 문제에 자주 막히게 되었습니다
이 개념에 대해 잘 모르는 채로 풀고 있었기 때문이라 생각되어 DP에 대해 한 번 알아보고 문제를 풀어보겠습니다

---

1. 동적 계획법

동적 계획법 : Dynamic Programming (DP)

‘동적 계획법’은 프로그래밍 문제에 자주 출현되는 개념 중 하나입니다
동적 계획법의 큰 특징은 큰 문제를 작게 나누어 풀이를 한다는 점이라 볼 수 있겠습니다

가장 대표적인 예시로는 ‘피보나치(Fibonacci)’ 수열이 있습니다

피보나치 수열은 1, 1, 2, 3, 5, 8, 13, … 값을 가지며 n > 3인 n번째 항 F_n에 대해
앞의 두 항의 합 F_n = F_(n-2) + F_(n-1)으로 나타낼 수 있습니다

1-1. DP / Top-Down

static int[] arr;

public static int fibonacci(int n) {
    if (n <= 2)
        return 1;
    if (arr[n] == 0)
        arr[n] = fibonacci(n-2) + fibonacci(n-1);

    return arr[n];
}

public static void main(String[] args) {
    int n = 10;             // n을 입력받은 경우
    int result;

    arr = new int[n+1];     // 피보나치 수열의 index를 0이 아닌 1부터 진행하므로 1 추가
    result = fibonacci(arr);

    System.out.println("피보나치 수열의 " + n + "번째 값 : " + result);
    // 출력 : "피보나치 수열의 10번째 값 : 55"
}

평범하게 재귀 함수로 푸는 문제처럼 보이지만 여기서는 static int[] arr;을 사용하고 있습니다
그리고 fibonacci가 실행되면 배열에 이미 계산된 값을 저장하면서 굳이 했던 계산을 더 할 필요가 없어졌구요

위 예시의 재귀 함수처럼 큰 문제를 풀기 위해 아래로 내려가며 풀어 나아가는 방법을 ‘Top-Down’이라 합니다

배열을 사용하지 않고 재귀 함수로 푼다면 같은 함수를 여러 번 실행시키기에 중복 연산이 많아지면서
시간 복잡도(Time Complexity)마저 매우 커지기 때문에 비효율적인 알고리즘이 됩니다

1-2. Bottom-Up

Top-Down의 반대인 Bottom-Up은 작은 문제부터 구하고자 하는 문제까지 올라가며 푸는 방법으로
재귀 함수를 사용하던 Top-Down과는 다르게 Bottom-Up은 반복문으로 구현하는 경우가 일반적입니다

public static int fibonacci(int n) {
    int[] arr = new int[n+1];

    // 피보나치 수열의 1, 2번째 항 초기화
    arr[1] = 1;
    arr[2] = 1;

    for (int i=3; i<=n; i++)
        arr[i] = arr[i-1] + arr[i-2];

    return arr[n];
}

public static void main(String[] args) {
    int n = 10;             // n을 입력받은 경우
    int result = fibonacci(10);

    System.out.println("피보나치 수열의 " + n + "번째 값 : " + result);
    // 출력 : "피보나치 수열의 10번째 값 : 55"
}

Bottom-Up의 경우, 수열을 사용하기 위해 필요한 항만 미리 대입한 뒤
반복문으로 차근차근 올라가면서 이전에 저장해둔 값으로 계산을 하다가 큰 문제를 풀게 됩니다

---

2. DP를 이용해 문제 하나 더 풀어보기

2-1. 백준 11053 - 가장 긴 증가하는 부분 수열

알고리즘 분류가 ‘다이나믹 프로그래밍(DP)’인 백준 11053번 - 가장 긴 증가하는 부분 수열을 풀어봅시다

• 문제
  • 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
  • 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
• 입력
  • 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
  • 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

2-2. 문제 풀이

int[] dp = new int[N];

조건(증가하는 부분)에 만족하는 수열의 개수를 dp[N]에 저장해봅시다

for (int i=0; i<N; i++) {
    // 부분 수열의 개수는 반드시 1개 포함이므로 1 대입
    dp[i] = 1; 
}

이제 i = [0, N) 범위로 반복문을 실행시키면서, [0, i] 범위 내에 오름차순이 얼마나 있는지 확인해볼 것입니다
예를 들어, {10, 20, 10, 30}이면 다음처럼 확인해야 합니다

1. 10
2. 10 -> 20
3. 10
4. 10 -> 20 -> 30

for (int i=0; i<N; i++) {
    dp[i] = 1;

    // A[j]가 A[i]보다 작고, dp[i]가 dp[j+1]보다 작으면
    // dp[i]에 dp[j] + 1 대입
    for (int j=0; j<i; j++) {
        if (A[j] < A[i] && dp[i] < dp[j] + 1)
            dp[i] = dp[j] + 1;
    }
}

다시 dp에 값을 넣으면서 확인해보자면

1. dp[0] : 1
2. dp[1] : 2 // A[0] < A[1]이고 dp[1] < dp[0]+1 이므로 dp[0] + 1 대입
3. dp[2] : 1
4. dp[3] : 3 // A[1] < A[3]이고 dp[3] < dp[1]+1 이므로 dp[1] + 1 대입
   • j = 2일 때, (dp[3] < dp[2]+1) -> (3 < 1+1)은 거짓이므로 실행X

{10, 20, 10, 30}에서 30을 탐색하는 타이밍에 {10, 20}이 제일 많은 수열이었으므로 2+1 -> 3 대입

즉, 순회하면서 이전의 요소들 중 dp가 가장 높은 값보다 더 높으면 거기에 +1을 적용하게 되는 것입니다

2-3. 답안

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // 숫자 입력
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(st.nextToken());

        // Dynamic Programming을 위한 배열 추가 (Bottom-Up 방식)
        int[] dp = new int[N];

        for (int i=0; i<N; i++) {
            dp[i] = 1;

            // 0번째부터 i번째 까지 수열 탐색
            for (int j=0; j<i; j++) {
                if (A[j] < A[i] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
            }
        }

        // dp중 최댓값 출력
        bw.write(Arrays.stream(dp).max().getAsInt() + "\n");
        bw.flush();

        br.close();
        bw.close();
    }
}

최댓값을 출력하는 부분은 알맞게 사용하면 되겠습니다
저는 간단하게 스트림의 max()를 사용하여 최댓값을 추출하였습니다