[JAVA] 다이나믹 프로그래밍 (Dynamic Programming)

목차

• 다이나믹 프로그래밍의 조건
  • 비효율적인 피보나치 수열 구현
  • 탑다운 방식으로 피보나치 수열 구현
  • 바텀업 방식으로 피보나치 수열 구현
• 예제 풀이
  • 개미 전사
    • 문제
    • 아이디어
    • 문제 풀이
  • 1로 만들기
    • 문제
    • 아이디어
    • 문제 풀이
    • 디버깅
  • 효율적인 화폐 구성
    • 문제
    • 아이디어
    • 문제 풀이
    • 디버깅

다이나믹 프로그래밍의 조건

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.

비효율적인 피보나치 수열 구현

import java.util.*;

public class Main {

    // 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
    public static int fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return fibo(x - 1) + fibo(x - 2);
    }

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

탑다운 방식으로 피보나치 수열 구현

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));
    }
}

바텀업 방식으로 피보나치 수열 구현

import java.util.*;

public class Main {

    public static long[] d = new long[100];

    public static void main(String[] args) {
    
    	// 점화식에서의 첫번째 항과 두번째 항을 초기화해줄 수 있도록 함.
        // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
        d[1] = 1;
        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]);
    }
}

작은 문제를 해결해놓은 다음, 그 작은 문제들을 이용해 앞으로의 큰 문제들을 차례대로 해결해나가는 방식

예제 풀이

개미 전사

문제

아이디어

- 바텀업 방식으로 0부터 차례대로 올라가면서 n번째 식량창고를 선택했을 때, 얻을 수 있는 식량의 최대값을 구해 저장해놓는다.

- 저장해놓은 값을 이용한다

- 현재(i번째) 식량 창고를 털려면 i-2번 식량 창고를 털어야 한다.

다시 말해, i-2번 식량 창고를 선택하였을 때 얻을 수 있는 식량의 최대값을 저장해놓았을 테니, 해당 값과 i번째 식량 창고의 값을 더하면 된다.

 

- i-1번 식량 창고를 털면 현재(i번째) 식량 창고를 털 수 없다.

 

- 따라서 i-1 과 i-2 + i 값을 비교하여 더 큰 값이 i번째에 얻을 수 있는 식량의 최대값이 된다.

 

- 이는 다이나믹 프로그래밍의 조건을 만족한다.

    1. 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황

    2. 각 부분의 문제들이 서로 영향을 미치며 부분 문제가 중복됨

문제 풀이

import java.util.*;

public class Main {

    // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
    public static int[] restoreData = new int[100];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 정수 N을 입력받기
        int n = sc.nextInt();

        // 모든 식량 정보 입력받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        // 0번과 1번 데이터는 문제 조건에 의해 따로 계산할 필요 없이 바로 들어갈 수 있음
        restoreData[0] = arr[0];
        restoreData[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < n; i++) {
            restoreData[i] = Math.max(restoreData[i - 1], restoreData[i - 2] + arr[i]);
        }

        // 계산된 결과 출력) 답에서 원하는 i번째 == n-1 과 동일
        System.out.println(restoreData[n - 1]);
    }
}

1로 만들기

문제

아이디어

- 바텀업 방식으로 문제를 해결해볼 수 있을 것 같다.

- 정수 x의 범위가 3만까지니까, 3만1개의 배열을 만들어 해당 인덱스값의 횟수를 기록해두면 될듯.

- 1의 연산횟수 -> d[1] = 0

- 2의 연산횟수 -> 1을 뺀 값과, 5또는 3또는 2로 나눈 인덱스의 횟수를 비교하여 더 적은 값

문제 풀이

import java.util.*;

public class Main {

    // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
    // d[1] 의 경우, 1은 따로 연산을 할 필요가 없으므로 0회 그대로 들어간다고 친다
    public static int[] d = new int[30001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();

        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        for (int i = 2; i <= x; i++) {
            // 현재의 수에서 1을 빼는 경우
            d[i] = d[i - 1] + 1;
            // 현재의 수가 2로 나누어 떨어지는 경우
            if (i % 2 == 0)
                d[i] = Math.min(d[i], d[i / 2] + 1);
            // 현재의 수가 3으로 나누어 떨어지는 경우
            if (i % 3 == 0)
                d[i] = Math.min(d[i], d[i / 3] + 1);
            // 현재의 수가 5로 나누어 떨어지는 경우
            if (i % 5 == 0)
                d[i] = Math.min(d[i], d[i / 5] + 1);

            System.out.println(String.format("d[%d] = " + d[i], i));
        }

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

디버깅

26
d[2] = 1
d[3] = 1
d[4] = 2
d[5] = 1
d[6] = 2
d[7] = 3
d[8] = 3
d[9] = 2
d[10] = 2
d[11] = 3
d[12] = 3
d[13] = 4
d[14] = 4
d[15] = 2
d[16] = 3
d[17] = 4
d[18] = 3
d[19] = 4
d[20] = 3
d[21] = 4
d[22] = 4
d[23] = 5
d[24] = 4
d[25] = 2
d[26] = 3
3

효율적인 화폐 구성

문제

아이디어

- 바텀업 방식으로 M원이 될때까지 각 원(₩)마다 최소횟수를 구해 저장해놓기

- INF는 될 수없는 수로 해놓기

- 초기 설정

- 첫번째 화폐 단위인 2 확인할때, 인덱스에서 화폐 단위인 2를 뺀 값이 10001이 아니면 현재 값(10001 또는.. 뭐 화폐단위가 1이 있었으면 2가 들어있었을듯.) 과 인덱스에서 화폐 단위인 2를 뺀 값에서 1을 더한 값을 비교하여 작은값을 설정

- 같은 방식으로 3도 확인

- 5의 경우, 인덱스 5에서 3을 뺀 인덱스 2의 값이 1로 존재하므로, +1한 2가 값으로 들어갈 수 있게 됨. 

- 6의 경우, 2로 나눴을때의 값인 3보다 3으로 나눴을때의 값인 2가 더 작으므로 2로 바뀐것을 볼 수 있음.

- 7의 경우, 인덱스7에서 3을 뺀 인덱스 4의 값이 2로 존재하므로, +1한 3이 값으로 들어갈 수 있게 됨.

- 5 확인

- 7의 경우, 인덱스 7에서 5를 뺀 2의 값이 1로존재하므로 +1한 2가 들어갈 수 있게 됨. 기존에 3이였던 값보다 더 작기도 하고. 

문제 풀이

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 정수 N, M을 입력받기
        int n = sc.nextInt();
        int m = sc.nextInt();

        // N개의 화폐 단위 정보를 입력 받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
        // 절대 나올 수 없는 값인 10001을 배열의 기본값으로 넣어둔다. (문제 입력 조건 M값의 범위가 1이상 10000이하)
        int[] d = new int[m + 1];
        Arrays.fill(d, 10001);

        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        d[0] = 0;
        for (int i = 0; i < n; i++) {
            //각각의 화폐를 돌며 최소값 확인
            System.out.println(String.format("**** %d 원짜리 화폐 확인 ****", arr[i]));
            for (int j = arr[i]; j <= m; j++) {
                // (i - k)원을 만드는 방법이 존재하는 경우
                if (d[j - arr[i]] != 10001) {
                    System.out.println(String.format("화폐 금액을 뺀 %d인덱스의 값 %d이 10001이 아니므로 %d원을 만드는 방법 존재, %d원과 화폐 금액을 뺸 %d 비교",j-arr[i], d[j-arr[i]], j, j, j-arr[i]));
                    d[j] = Math.min(d[j], d[j - arr[i]] + 1);
                    System.out.println(String.format("%d 회", d[j]));
                }
            }
        }

        // 계산된 결과 출력
        if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
            System.out.println(-1);
        }
        else {
            System.out.println(d[m]);
        }
    }
}

디버깅

3 7
2 3 5
**** 2 원짜리 화폐 확인 ****
화폐 금액을 뺀 0인덱스의 값 0이 10001이 아니므로 2원을 만드는 방법 존재, 2원과 화폐 금액을 뺸 0 비교
1 회
화폐 금액을 뺀 2인덱스의 값 1이 10001이 아니므로 4원을 만드는 방법 존재, 4원과 화폐 금액을 뺸 2 비교
2 회
화폐 금액을 뺀 4인덱스의 값 2이 10001이 아니므로 6원을 만드는 방법 존재, 6원과 화폐 금액을 뺸 4 비교
3 회
**** 3 원짜리 화폐 확인 ****
화폐 금액을 뺀 0인덱스의 값 0이 10001이 아니므로 3원을 만드는 방법 존재, 3원과 화폐 금액을 뺸 0 비교
1 회
화폐 금액을 뺀 2인덱스의 값 1이 10001이 아니므로 5원을 만드는 방법 존재, 5원과 화폐 금액을 뺸 2 비교
2 회
화폐 금액을 뺀 3인덱스의 값 1이 10001이 아니므로 6원을 만드는 방법 존재, 6원과 화폐 금액을 뺸 3 비교
2 회
화폐 금액을 뺀 4인덱스의 값 2이 10001이 아니므로 7원을 만드는 방법 존재, 7원과 화폐 금액을 뺸 4 비교
3 회
**** 5 원짜리 화폐 확인 ****
화폐 금액을 뺀 0인덱스의 값 0이 10001이 아니므로 5원을 만드는 방법 존재, 5원과 화폐 금액을 뺸 0 비교
1 회
화폐 금액을 뺀 2인덱스의 값 1이 10001이 아니므로 7원을 만드는 방법 존재, 7원과 화폐 금액을 뺸 2 비교
2 회
2