ETC/자료구조 이론

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

지과쌤 2022. 9. 19.

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

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

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

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

저작자표시 비영리 변경금지

'ETC > 자료구조 이론' 카테고리의 다른 글

[자료구조] Queue(큐) - Java, Python (0)	2021.08.16
[자료구조] Stack(스택) - Java, Python (0)	2021.08.14
[JAVA] 순차탐색(Sequential Search), 이진탐색(Binary Search) (0)	2020.09.08

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

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

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

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

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

예제 풀이

개미 전사

문제

아이디어

문제 풀이

1로 만들기

문제

아이디어

문제 풀이

디버깅

효율적인 화폐 구성

문제

아이디어

문제 풀이

디버깅

'ETC > 자료구조 이론' 카테고리의 다른 글

댓글

💲 추천 글

티스토리툴바

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

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

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

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

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

예제 풀이

개미 전사

문제

아이디어

문제 풀이

1로 만들기

문제

아이디어

문제 풀이

디버깅

효율적인 화폐 구성

문제

아이디어

문제 풀이

디버깅

'ETC > 자료구조 이론' 카테고리의 다른 글

볼 만한 글

댓글

💲 추천 글

티스토리툴바