5주차 알고리즘 복습 - 다이나믹 프로그래밍

다이나믹 프로그래밍 (Dynamic Programming) DP , 동적 계획법

 - 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하여 문제의 답을 구함

    여기까지는 분할정복인데                                                  여기서 차이가 있음.

 - 중간 계산 결과를 기록하기 위한 메모리가 필요

 - 한 번 계산한 부분을 다시 계산하지 않아 속도가 빠름

 

* 다른 알고리즘과의 차이점

 - 분할정복과의 차이점 

     : 분할정복은 부분문제가 중복되지 않음

     : DP는 부분문제가 중복되어 재활용에 사용

 

 - 그리디 알고리즘과의 차이점

    : 그리디는 순간의 최선을 구하는 방식 (최적해)

    : DP는 모든 방법을 확인 후 최적해 구하는 방식 -> 그 과정에서 중복된 연산을 하지 않음

 

* 그리디가 DP보다 빠름 (당연함)

반드시 최적해를 구해야하고 그리디 적용할 수 없는 케이스들에서는 DP (모든 방법 확인 + 중복된 연산 하지 않으므로 시간 절약)

 

동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다.

 

- 다이나믹 프로그래밍 예시

피보나치

 

- 다이나믹 프로그래밍 방법

· 타뷸레이션 (Tabulation) Bottom-up방식

  : 상향식 접근 방법

  : 작은 하위 문제부터 풀면서 올라감

  : 모두 계산하면서 차례대로 진행

  ex) 피보나치 수열에서 f(1), f(2)... 를 저장해놓고 후에 필요하면 저장된 값 씀

 

· 메모이제이션 (Memoization) Top-down 방식 -> 재귀함수 기반으로 돌아야함

  : 하향식 접근 방법

  : 큰 문제에서 하위 문제를 확인해가며 진행

  : 계산이 필요한 순간 계산하며 진행 

  ex) 피보나치 수열에서 f(5)를 구할 때 필요한 f(4), f(3)을 확인하고 필요하면 연산 수행.

 

---

피보나치 수열 실습

import java.util.*;

public class Practice {
    public static int fib(int n) {
        if (n <= 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }
    public static int fibDP(int n) {
        int dp[] = new int[n];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < n; i++) {
            dp[i] = dp[i -1] + dp[i - 2];
        }
        return dp[n - 1];
    }
    static int dp[] = new int[8];
    public static int fibDP2(int n) {
        if (n <= 2) return 1;
        if (dp[n] != 0) {
            return dp[n];
        } else {
            dp[n] = fibDP2(n -1) + fibDP2(n - 2);
        }
        return dp[n];
    }

        public static void main(String[] args) {
        // Test code
        System.out.println(fib(7));
        System.out.println(fibDP(7));
        System.out.println(fibDP2(7));
    }
}

---

Practice 1)

// 정수 n 이 주어졌을 때 아래의 연산을 통해 1로 만들려고 한다.
// 2로 나누어 떨어지면 2로 나누기
// 3으로 나누어 떨어지면 3으로 나누기
// 1 빼기
// 위의 연산을 통해 1로 만들 때 필요한 최소한의 연산 횟수를 출력하는 프로그램을 작성하세요.

// 입출력 예시
// n: 2
// 출력: 1

// n: 9
// 출력: 2

* 그리디에서 풀었던 문제랑 비슷하다.

여기서는 1부터 시작해서 1을 만들 때 필요한 연산 값들을 미리 dp[]에 저장해놔야함.

먼저 dp[i] = dp[i - 1] + 1;을 통해 1을 뺐을 때의 연산 횟수를 저장해줌.

조건문을 통해 2로 나누어 떨어지면 2로 나누어 떨어졌을 때 그 값이 저장돼있던 dp 에 + 1한 값과 -1해서 저장해놓은 원본 dp[i] 중에 더 작은 값을 선택함.

import java.util.*;

public class Practice {
    public static int solution(int n) {
        int dp[] = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; // - 1한 경우를 먼저 dp에 넣어놓고

            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            } else if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        // Test code
        System.out.println(solution(2));    // 1
        System.out.println(solution(4));    // 2
        System.out.println(solution(9));    // 2
        System.out.println(solution(10));   // 3
    }
}

---

Practice 2 )

// 수열 arr 이 주어졌을 때,
// 부분 수열 중 증가하는 부분이 가장 긴 길이를 출력하는 프로그램을 작성하세요.

// 입출력 예시
// arr: {10, 20, 30, 10, 50, 10}
// 출력: 4

* dp테이블에 각 인덱스마다 증가하면 이전 값에서 +1을 해주고 감소하는 부분에는 0을 넣는다.

라고 생각했는데 출력이 4인 것을 보니 i에서 i + 1로 증가할 때의 가장 큰 차이값을 갖는 인덱스를 출력하라는 문제다.

라고 또 생각했는데 그게 아니고 10, 20, 30에서 증가하는 부분이 3이고 10으로 감소했다가 50으로 또 증가하니까 4임..

문제 설명이 좀 이상하네 암튼 풀긴했는데 어렵당

import java.util.*;
import java.util.stream.IntStream;

public class Practice {
    public static int solution(int arr[]) {
        int n = arr.length;
        int dp[] = new int[n + 1];
        int result = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = 1;

            for (int j = 1; j < i; j++) {
                if (arr[j - 1] < arr[i - 1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
    public static void main(String[] args) {
        // Test code
        int[] arr = new int[]{10, 20, 30, 10, 50, 10};
        System.out.println(solution(arr));
    }
}

---

Practice 3)

// 배낭에 물품을 담으려고 한다.
// 배낭에는 k 무게 만큼의 물품을 담을 수 있다.
// n 개의 물품이 주어지고 이 물품의 무게와 가치 정보가 items 2차원 배열에 주어졌을 때,
// 최대 가치가 되도록 물품을 담았을 때의 가치를 출력하는 프로그램을 작성하세요.

// 입출력 예시
// items: {{6, 13}, {4, 8}, {3, 6}, {5, 12}}
// n: 4
// k: 7
// 출력: 14

* 모든 경우의 수를 구해보고 최대 가치를 찾아야함.

부분 문제로 풀 수 있는지 보고 겹치는 부분을 찾기

Tabulation방법으로 dp테이블을 1 2 3 4 5 6 7 

 1. 무게별로 정렬

 2. 무게에 해당하는 최대 가치를 저장 (작은 무게의 데이터부터 삽입)

Math.max부분이 좀 헷갈리지만 이해하려고 노력 중..

import java.util.*;
import java.util.stream.IntStream;

public class Practice {
    public static int solution(int items[][], int n, int k) {
        Arrays.sort(items, (x, y) -> x[0] - y[0]);
        int dp[][] = new int[n + 1][k + 1];

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                if (items[i][0] > j){
                    dp[i + 1][j] = dp[i][j];
                    //지금 넣으려고 하는 무게가 J 현재 넣을 무게 칸보다 큰 경우
                    // 이전에 있던 값이 내려오는 부분
                } else {//물건을 넣을 수 있는 경우
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - items[i][0]] + items[i][1]);
                    //기존 위에 있는 값이랑 DP에서 7 - 현재 넣을 무게(4)만큼 뺀 곳에 값이 있는 가치 + 현재넣을 무게의 가치 중 큰 값으로 업데이트
                }
            }
        }
        return dp[n][k];
    }
    public static void main(String[] args) {
        // Test code
        int[][] items = {{6, 13}, {4, 8}, {3, 6}, {5, 12}};
        System.out.println(solution(items, 4, 7));  // 14
    }
}

---

힌트문제 

(백준/자바) 힌트문제3 02. 2차원배열 - 백준 2167번 문제 : 2차원 배열의 합 (tistory.com)

(백준/자바) 힌트문제3 02. 2차원배열 - 백준 2167번 문제 : 2차원 배열의 합

(백준/자바) 힌트문제3 04. 다이나믹 프로그래밍 - 백준 1890번 문제 : 점프 (tistory.com)

(백준/자바) 힌트문제3 04. 다이나믹 프로그래밍 - 백준 1890번 문제 : 점프