[Algorithm/Concept] Dynamic Programming

공부 자료

바킹독 블로그 [실전 알고리즘] 0x10강 - 다이나믹 프로그래밍

 

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

여러 개의 하위 문제를 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

 

문제를 해결하기 위한 점화식을 찾아낸 후, 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘 가장 유명한 예: 피보나치 수열

 

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

BOJ 1463번: 1로 만들기

import java.util.Scanner;

public class Main {
    static int d[];
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // 1. 테이블 정의하기: d[i] = i를 1로 만드는 최소 연산 횟수
        d = new int[N+1];
        // 2. 점화식
        /*
        d[k] = min(d[k/3],d[k/2],d[k-1]) +1 (단 k/3 -> 3으로 나누어질때, k/2 -> 2로 나누어질 때)
         */
        // 3. 초기값
        d[0] = 1;

        for (int i = 2; i < N + 1; i++) {
            d[i] = d[i - 1] + 1;
            if (i % 2 == 0) {
                d[i] = Math.min(d[i], d[i / 2] + 1);
            }
            if (i % 3 == 0) {
                d[i] = Math.min(d[i], d[i / 3] + 1);
            }
        }
        System.out.println(d[N]);
    }
}

BOJ 9095: 1, 2, 3 더하기

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int d[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        //1. 테이블 정의하기
        // d[i] = 1,2,3으로 i를 표현하는 경우의 수
        d = new int[12];
        Arrays.fill(d, -1);

        //2. 점화식 세우기
        // d[k] = d[k-1] + (k-2)

        //3. 초기값
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;

        for (int t = 0; t < T; t++) {
            int N = sc.nextInt();
            if (d[N] != -1) {
                System.out.println(d[N]);
            } else {
                for (int n = 1; n < N + 1; n++) {
                    if (d[n] != -1) {
                        continue;
                    }
                    d[n] = d[n - 1] + d[n - 2] + d[n - 3];
                }
                System.out.println(d[N]);
            }
        }

    }
}

BOJ 2579: 계단 오르기

import java.util.Arrays;
import java.util.Scanner;

import static java.util.Arrays.stream;

public class Main {
    static long d[];
    static long stair[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int stairN = sc.nextInt();
        // 1. 테이블 정의: d[i] = i번째 계단을 밟을 때의 최대값
        // 2. 점화식: d[k] = max(d[k-2] + stair[k], d[k-3] + stair[k-1] + stair[k])
        d = new long[301];
        Arrays.fill(d,0);
        stair = new long[301];

        for (int n = 1; n < stairN + 1; n++) {
            long t = sc.nextLong();
            stair[n]=t;
        }

        d[1] = stair[1];
        d[2] = stair[1] + stair[2];
        d[3] = Math.max(stair[1] + stair[3], stair[2] + stair[3]);

        for (int n = 4; n < stairN+1; n++) {
            d[n] = Math.max(d[n - 2], d[n - 3] + stair[n - 1]) + stair[n];
        }

        System.out.println(d[stairN]);
    }
}

BOJ 1149: RGB거리

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int d[][];
    static int cost[][];
    public static void main(String[] args) throws IOException {
        d = new int[1001][3];
        cost = new int[1001][3];
        // 1. 테이블 정의하기
        // d[i][j]: i번째 집이 j번째 색깔을 칠할 때, 1~i번째까지 집의 총합

        // 2. 점화식 구하기
        // d[i][j_A] = min(d[i][j_B], d[i][j_C]) + cost[i][j_A]

        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));

        int houseNum = Integer.parseInt(br.readLine());

        for (int i = 1; i < houseNum+1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i][0] = Integer.parseInt(st.nextToken());
            cost[i][1] = Integer.parseInt(st.nextToken());
            cost[i][2] = Integer.parseInt(st.nextToken());
        }


        // 3. 초기값
        d[1][0] = cost[1][0];
        d[1][1] = cost[1][1];
        d[1][2] = cost[1][2];

        for (int i = 2; i < houseNum + 1; i++) {
            for (int j = 0; j < 3; j++) {
                d[i][j] = Math.min(d[i - 1][(j + 1) % 3], d[i - 1][(j + 2) % 3]) + cost[i][j];
            }
        }
        System.out.println(Math.min(d[houseNum][0], Math.min(d[houseNum][1],d[houseNum][2])));
    }
}

BOJ 11726: 2 x n 타일링

import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int d[];
    static int MOD = 10_007;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 1. 테이블 정의하기: d[i]: i번째까지의 모든 경우의 수
        d = new int[1001];
        // 2. 점화식 구하기: d[k] = d[k-1] + d[k-2]
        // 3. 초기값
        d[1]=1;
        d[2]=2;
        if (n == 1 || n == 2) {
            System.out.println(d[n]);
        } else {
            for (int i = 3; i < n + 1; i++) {
                d[i] = (d[i - 1] + d[i - 2] )% MOD;
            }
            System.out.println(d[n]);
        }

    }
}

BOJ 11659: 구간 합 구하기 4

package baek11659;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    // 1. 테이블 정의: d[k] = k번째 까지의 sum 값
    // 2. 점화식: d[k] = d[k-1] + cost[k]
    // a ~ b 까지의 sum값: d[b] - d[a-1]
    // 초깃값
    // d[0] = 0
    // d[1] = cost[k]
    static long d[];
    static int cost[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        d = new long[n + 1];
        cost = new int[n+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n + 1; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }
        d[0] = 0;
        d[1] = cost[1];

        for (int i = 1; i < n + 1; i++) {
            d[i] = d[i - 1] + cost[i];
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            System.out.println(d[end]-d[start-1]);
        }
    }
}

BOJ 12852: 1로 만들기 2

package baek12852;

import java.util.Scanner;

public class Main {
    static int preIndex[];
    static int d[];

    static int MAX = 100_000_0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        preIndex = new int[MAX + 1];
        d = new int[MAX + 1];

        d[0]=0;
        d[1]=0;
        d[2]=1;
        d[3]=1;
        preIndex[0]=0;
        preIndex[1]=0;
        preIndex[2]=1;
        preIndex[3]=1;

        for (int i = 4; i < n + 1; i++) {
            d[i] = d[i - 1]+1;
            preIndex[i] = i-1;

            if (i % 2 == 0 && d[i/2]+1 < d[i]) {
                d[i] = d[i / 2] + 1;
                preIndex[i] = i / 2;
            }
            if (i % 3 == 0 && d[i/3]+1 < d[i]) {
                d[i] = d[i/3] +1;
                preIndex[i] = i / 3;
            }
        }
        System.out.println(d[n]);
        int p = n;
        while (p > 0) {
            System.out.print(p + " ");
            p = preIndex[p];
        }

    }
}

preIndex라는 배열을 새롭게 생성해, 최적의 이전 위치 인덱스값을 저장하는 아이디어가 핵심입니다.