# 동적계획법 (DP, Dynamic Programming)

## 동적계획법이란?


- 중복되는 계산을 피하며, 최적해를 구하기 위해 작은 하위 문제들의 해결 결과를 저장하고 활용하는 알고리즘 설계 기법
- 동적 계획법은 큰 문제를 해결하기 위해 작은 하위 문제들의 최적해를 계산하는 과정을 반복하여 전체 문제의 최적해를 구한다. 이를 위해 다음과 같은 단계로 구성된다
1. 작은 규모의 하위 문제들로 분할: 원래 문제를 작은 크기의 하위 문제들로 분할한다.
2. 하위 문제들의 최적해 계산: 각 하위 문제들의 최적해를 계산한다. 이때, 중복 계산을 피하기 위해 **계산 결과를 저장**(메모이제이션)한다.
3. 최적해 조합: 계산된 하위 문제들의 최적해를 활용하여 전체 문제의 최적해를 조합한다.
4. 결과 반환: 전체 문제의 최적해를 반환하거나 필요에 따라 저장한다.
- 동적 계획법은 최적 부분 구조와 중복 부분 문제라는 두 가지 핵심 개념에 기반을 두고 있다. 최적 부분 구조는 큰 문제의 최적해가 작은 하위 문제들의 최적해로 구성될 수 있는 성질을 의미하며, 중복 부분 문제는 작은 규모의 하위 문제들이 서로 중복되어 반복해서 해결되는 성질을 의미한다.
- 장점
- 중복 계산을 피할 수 있음
- 최적 부분 구조 활용 가능
- 다양한 문제에 적용 가능
- 문제의 크기에 따라 Bottom-up 또는 Top-down 방식 선택 가능
- Bottom-up : 작은 하위 문제부터 순차적으로 계산하며 전체 문제의 최적해를 구하는 방법
- Top-down : 큰 문제를 해결하기 위해 재귀적으로 하위 문제들을 해결하는 방법
- 최적해 보장
- 단점
- 필요 메모리 공간 증가
- 하위 문제의 의존성
- 동적 계획법은 하위 문제들 간의 의존성이 있는 경우에 적용된다. 만약 하위 문제들이 서로 독립적이거나 의존성이 적다면 동적 계획법이 적합하지 않을 수 있다.
- 최적 부분 구조의 확보
- 동적 계획법을 적용하기 위해서는 최적 부분 구조가 보장되어야 한다. 최적 부분 구조가 없는 문제에 동적 계획법을 적용하면 부분 문제들의 최적해를 조합하여 전체 문제의 최적해를 구할 수 없다.

### 메모이제이션 (Memoization)

- 함수가 이전에 계산한 값을 기억하고, 동일한 입력이 들어오면 미리 계산한 값을 반환하여 중복 계산을 방지하는 기법
- 재귀 알고리즘의 효율성을 높이기 위한 방법 중 하나
- 동적계획법 알고리즘에서 중요한 역할을 하는 개념

## 동적 계획법 예시

1. 피보나치 수열
2. 2×n 타일링 문제
- 2×1 타일로 2×n 직사각형을 채우는 방법의 수를 구하는 문제
- 백준 알고리즘 11726번 ==[링크](https://www.acmicpc.net/problem/11726)==
3. 쉬운 계단 수 문제
- 인접한 자리의 수가 1씩 차이나는 수를 계단 수라고 한다. N자리 수 중에서 계단 수인 수의 개수를 구하는 문제
- 백준 알고리즘 10844번 ==[링크](https://www.acmicpc.net/problem/10844)==
4. 평범한 배낭 문제
- 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하는 문제
- 백준 알고리즘 12865번 ==[링크](https://www.acmicpc.net/problem/12865)==

### 피보나치 수열


#### 재귀 함수를 사용한 피보나치 수열

public class FibonacciRecursive {

    // 재귀 함수를 사용하여 피보나치 수열을 계산하는 함수
    public static int fibonacci(int n) {
        if (n <= 1) { // 피보나치 수열의 첫 번째와 두 번째 항은 해당 인덱스 값과 동일
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // 이전 두 항의 합으로 다음 항을 계산
        }
    }

    public static void main(String[] args) {
        int n = 10;
        for (int i = 0; i <= n; i++) {
            System.out.print(fibonacci(i) + " "); // 0부터 n까지의 피보나치 수열 출력
        }
    }
}

#### 동적계획법을 사용한 피보니차 수열 (Top-down 방식)

public class FibonacciDynamicProgramming {

    private static int[] fibMemo; // 계산된 결과를 저장할 static 변수

    public static int fibonacciTopDown(int n) {
        if (fibMemo[n] != -1) { // 이미 계산된 결과가 있다면 해당 값을 반환
            return fibMemo[n];
        }

        if (n <= 1) {
            return n;
        } else {
            fibMemo[n] = fibonacciTopDown(n - 1) + fibonacciTopDown(n - 2); // 계산 결과를 저장
            return fibMemo[n];
        }
    }

    public static void main(String[] args) {
        int n = 10;
        fibMemo = new int[n + 1];
        Arrays.fill(fibMemo, -1); // 초기값 -1로 설정

        for (int i = 0; i <= n; i++) {
            System.out.print(fibonacciTopDown(i) + " "); // 0부터 n까지의 피보나치 수열 출력
        }
    }
}

#### 동적계획법을 사용한 피보니차 수열 (Bottom-up 방식)

public class FibonacciDynamicProgramming {

    private static int[] fibMemo; // 계산된 결과를 저장할 static 변수

    public static int fibonacciBottomUp(int n) {
        fibMemo[0] = 0;
        fibMemo[1] = 1;

        for (int i = 2; i <= n; i++) {
            fibMemo[i] = fibMemo[i - 1] + fibMemo[i - 2]; // 계산 결과를 저장
        }

        return fibMemo[n];
    }

    public static void main(String[] args) {
        int n = 10;
        fibMemo = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            System.out.print(fibonacciBottomUp(i) + " "); // 0부터 n까지의 피보나치 수열 출력
        }
    }
}

> Top-down 방식 : 이미 계산된 결과를 확인하여 저장한 후 반환한다 (재귀 사용)
> Bottom-up 방식 : 작은 하위 문제부터 시작하여 계산 결과를 저장하고 최종 결과를 반환한다 (반복문 사용)

### 2×n 타일링 문제

- 백준 알고리즘 11726번 ==[링크](https://www.acmicpc.net/problem/11726)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 2×n 타일링 문제 수도코드 예

1. 타일의 가로 길이 N을 입력 받는다.
2. N개의 타일로 구성할 수 있는 2×N 직사각형의 개수를 저장할 배열을 초기화한다.
3. 가로 길이가 1인 경우, 2×1 직사각형 하나로 구성할 수 있으므로 1로 초기화한다.
4. 가로 길이가 2인 경우, 2×2 직사각형 하나 또는 1×2 타일 두 개로 구성할 수 있으므로 2로 초기화한다.
5. 가로 길이가 3부터 N까지 다음을 반복한다:
   - 현재 타일을 놓을 수 있는 경우의 수는 이전 타일에서 2×1 타일을 놓는 경우와 1×2 타일 두 개를 놓는 경우를 합한 값이다.
   - 현재 타일을 놓을 수 있는 경우의 수를 배열에 저장한다.
6. N개의 타일로 구성할 수 있는 2×N 직사각형의 개수를 출력한다.

#### 2×n 타일링 문제 소스코드 예

import java.util.Scanner;

public class Main {
    public static final int MOD = 10007; // 나누기 연산에 사용할 상수

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        if(N == 1){
            System.out.println(1);
            return;
        }
        
        int[] dp = new int[N + 1]; // N개의 타일로 구성할 수 있는 2×N 직사각형의 개수를 저장하는 배열
        
        // 초기값 설정: 가로 길이가 1인 경우 1, 가로 길이가 2인 경우 2
        dp[1] = 1;
        dp[2] = 2;

        // 가로 길이가 3부터 N까지 타일 개수 계산
        for (int i = 3; i <= N; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; // 이전 타일에서 2×1 타일을 놓는 경우와 1×2 타일 두 개를 놓는 경우를 합한 값
        }

        int answer = dp[N]; // N개의 타일로 구성할 수 있는 2×N 직사각형의 개수

        System.out.println(answer);

        scanner.close();
    }
}

### 쉬운 계단 수 문제

- 백준 알고리즘 10844번 ==[링크](https://www.acmicpc.net/problem/10844)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 쉬운 계단 수 문제 수도코드 예

1. 자릿수 N을 입력 받는다.
2. N자리 수를 갖는 계단 수의 개수를 저장할 배열을 초기화한다.
3. 첫 번째 자릿수는 1부터 9까지의 계단 수로 초기화한다.
4. 두 번째 자릿수부터 N번째 자릿수까지 다음을 반복한다:
   - 현재 자릿수에서 가능한 이전 자릿수의 숫자를 확인한다.
   - 이전 자릿수의 숫자가 0인 경우, 다음 자릿수는 1로 시작하는 계단 수만 가능하다.
   - 이전 자릿수의 숫자가 9인 경우, 다음 자릿수는 8로 시작하는 계단 수만 가능하다.
   - 이전 자릿수의 숫자가 1~8인 경우, 다음 자릿수는 이전 자릿수의 숫자 - 1 또는 이전 자릿수의 숫자 + 1로 시작하는 계단 수가 가능하다.
   - 현재 자릿수의 가능한 계단 수의 개수를 구하여 배열에 저장한다.
5. 배열에 저장된 N자리 수를 갖는 계단 수의 개수를 모두 더하여 결과를 출력한다.

#### 쉬운 계단 수 문제 소스코드 예

import java.util.Scanner;

public class Main {
    public static final int MOD = 1000000000; // 나누기 연산에 사용할 상수

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        long[][] dp = new long[N + 1][10]; // N자리 수를 갖는 계단 수의 개수를 저장하는 배열

        // 초기값 설정: 1자리 수는 1부터 9까지의 계단 수가 가능
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }

        // 두 번째 자릿수부터 N번째 자릿수까지 계단 수 개수 계산
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= 9; j++) {
                // 이전 자릿수의 숫자가 0인 경우, 다음 자릿수는 1로 시작하는 계단 수만 가능
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j + 1] % MOD;
                }
                // 이전 자릿수의 숫자가 9인 경우, 다음 자릿수는 8로 시작하는 계단 수만 가능
                else if (j == 9) {
                    dp[i][j] = dp[i - 1][j - 1] % MOD;
                }
                // 이전 자릿수의 숫자가 1~8인 경우, 다음 자릿수는 이전 자릿수의 숫자 - 1 또는 이전 자릿수의 숫자 + 1로 시작하는 계단 수가 가능
                else {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
                }
            }
        }

        long answer = 0;
        // N자리 수를 갖는 계단 수의 개수를 모두 더함
        for (int i = 0; i <= 9; i++) {
            answer = (answer + dp[N][i]) % MOD;
        }

        System.out.println(answer);

        scanner.close();
    }
}

### 평범한 배낭 문제

- 백준 알고리즘 12865번 ==[링크](https://www.acmicpc.net/problem/12865)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 평범한 배낭 수도코드 예

1. 물품의 수 N과 최대 무게 K를 입력 받는다.
2. 물품의 무게와 가치를 입력 받는다.
3. 물품을 담을 수 있는 최대 가치를 저장할 배열을 초기화한다.
4. 첫 번째 물품부터 N번째 물품까지 다음을 반복한다:
   - 현재 물품을 선택한 경우와 선택하지 않은 경우 중에서 가치가 더 큰 경우를 선택한다.
   - 현재 물품을 선택한 경우, 남은 무게가 물품의 무게보다 크거나 같은 경우에만 선택할 수 있다.
   - 현재 물품을 선택한 경우, 현재 물품의 가치와 이전에 선택한 물품까지의 가치를 더한 값을 저장한다.
   - 현재 물품을 선택하지 않은 경우, 이전까지의 최대 가치를 그대로 가져온다.
5. 물품을 선택한 경우와 선택하지 않은 경우 중에서 가치가 더 큰 값을 최대 가치로 선택한다.
6. 최대 가치를 출력한다.

#### 평범한 배낭 소스코드 예

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();

        int[] weights = new int[N + 1];
        int[] values = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            weights[i] = scanner.nextInt();
            values[i] = scanner.nextInt();
        }

        int[][] dp = new int[N + 1][K + 1]; // 물품을 담을 수 있는 최대 가치를 저장하는 배열

        // 물품을 선택할 수 있는 경우의 수마다 최대 가치 계산
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                // 현재 물품을 선택한 경우와 선택하지 않은 경우 중에서 가치가 더 큰 값을 선택
                if (weights[i] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        int answer = dp[N][K]; // 최대 가치

        System.out.println(answer);

        scanner.close();
    }
}