[알고리즘] DP (동적 계획법)

|  동적계획법이란?

- 복잡한 문제를 여러 개의 간단한 문제로 분리하여 해결하는 방법

- 원리 및 구현 방법

1) 큰 문제를 부분적으로 분리하여 분석한다

--> 부분적인 문제의 결과값은 항상 동일해야한다.

2) 1)을 통해 알게된 규칙을 통해 점화식을 생성한다.

3) 기존 배열과 dp배열을 어떻게 만들지 구상하고

4) 아래 두 가지 방법 중 적절한 구현 방법에 따라 수도 코드를 작성한다. 

타뷸레이션	= 바텀-업	- for문을 사용하여 구현
메모이제이션	= 탑-다운	* 이미지 출처 : 나무위키 - 재귀를 사용하여 구현

 

|  피보나치를 통해 보는 동적 계획법

- 점화식을 통해 재귀로 푼 피보나치 문제 풀이는 아래와 같았다.

// 피보나치 수열
// 재귀 (일반풀이 방법) - O(n^2), 계산했던 부분도 다시 계산
int fibonachi(int n) {
    if (n < 2) {
        return n;
    } else {
        return fib(n - 2) + fib(n - 1);
    }
}

- 타뷸레이션 방식으로 이를 풀게 되면, 1 1 2 3 5 8.. 순으로 데이터를 넣고 조회한다.

// 타뷸레이션 방식 - O(n)
int fibo2(int n) {
	// 재활용할 메모리 공간
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    
    for (int i = 1; i <= n; i++){
    	dp[i] = dp[i - 2] + dep[i - 1];
    }
    
    return dp[n];
}

- 메모이제이션을 사용하게 되면, Top-down 방식으로 재귀를 호출하는데,

  첫번째 방식과의 차이는 이미 확인한 데이터는 다시 하위로 깊이를 내려가 풀이 하지 않는다는 것이 다르다.

// 메모이제이션 방식 - O(n)
int[] dp = new int[8];
int fibo2(int n) {

    if (n <= 2) {
    	return 1;
    } 
    
    if (dp[n] != 0) {
    	return dp[n];
    }
    
    dp[n] = fibo2(n - 2) + fibo2(n - 1);
    
    return dp[n];
}

 

|  백준 문제풀이

1	1로 만들기	https://www.acmicpc.net/problem/1463	✅
2	퇴사	https://www.acmicpc.net/problem/14501	✅
3	이친수 구하기	https://www.acmicpc.net/problem/2193	✅
4	2*N 타일 구하기	https://www.acmicpc.net/problem/11726	✅
5	쉬운 계단 수	https://www.acmicpc.net/problem/10844	✅
6	연속된 정수의 합 구하기	https://www.acmicpc.net/problem/13398	✅
7	최장 공통 부분 수열 찾기
8	가장 큰 정사각형 찾기
9	빌딩 순서 구하기
10	DDR을 해보자
11	행렬 곱 연산 횟수의 최솟값 구하기
12	외판원의 순회 경로 짜기
13	가장 길게 증가하는 부분 수열 찾기

1. 1로 만들기

- 양의 정수 1~N까지를 아래의 점화식에 따라 풀이한 문제

D[i] = D[i - 1] + 1
if (2의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경
if (3의 배수) D[i / 3] + 1이 D[i]보다 작으면 변경

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex1463 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N : 구하고자 하는 수
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        dp[1] = 0;

        // * 규칙이 반복되는 구간은 2부터
        // for (i : 2 ~ N) {
        //    D[i] = D[i - 1] + 1 // 1을 뺀 점화시
        //    if (2의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경
        //    if (3의 배수) D[i / 3] + 1이 D[i]보다 작으면 변경
        // } 
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;

            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

        // 출력
        System.out.println(dp[N]);
    }
}

 

2. 퇴사

- dp에서 자주 나온다는 배낭 문제와 약간 비슷하나 다른 문제였다.

- 일련의 스케줄이 주어지고 기간 제약을 고려하여 최대 수익을 내는 문제

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

public class Ex14501 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 개의 스케줄을 각각의 일차원 배열에 받는다.
        int N = Integer.parseInt(br.readLine());

        // D 점화식 배열
        int[] D = new int[N + 2];

        // T 기간 배열
        int[] T = new int[N + 1];

        // P 수입 배열
        int[] P = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        // 터뷸레이션을 사용해서 D를 구한다.
        // D[i] = i날짜부터 n+1(퇴사일)까지 벌수 있는 최대 수익
        // for (i : N ~ 1){
        //    if (i+T[i]가 퇴사일보다 크면) D[i] = D[i + 1]
        //    if (i+T[i]가 퇴사일보다 크지 않으면) D[i] = Math.max(D[i + 1], P[i] + D[i + T[i]])
        // }
        for (int i = N; i >= 1; i--) {
            if (i + T[i] > N + 1) {
                D[i] = D[i + 1];
            } else {
                D[i] = Math.max(D[i + 1], D[i + T[i]] + P[i]);
            }
        }

        // 출력
        // D[1]
        System.out.println(D[1]);
    }
}

 

3. 이친수 구하기

- 욕 같지만 이진수를 만드는 특정 규칙를 지킨 수의 갯수를 구하는 문제였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex2193 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        // D 배열을 만든다 (2차원 배열)
        // dp[1][0] = 0, dp[1][1] = 1 초기화
        long[][] dp = new long[N + 1][2];
        dp[1][0] = 0;
        dp[1][1] = 1;

        // for (i : 2 ~ N) {
        //    dp[i][0] = dp[i - 1][0] + dp[i - 1][1] // 0은 0이나 1 뒤에 붙일 수 있다.
        //    dp[i][1] = dp[i - 1][0] // 1은 0 뒤에만 붙일 수 있다.
        // }
        for (int i = 2; i <= N; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            dp[i][1] = dp[i - 1][0];
        }

        System.out.println(dp[N][0] + dp[N][1]);
    }
}

 

... 나머지는 더 풀이를 하고 모르는 부분만 정리하여 올리려 한다.

위의 내용은 스스로 정리한 부분에 대해 이해할 수 있게 문제풀이한 것을 올린 내용..

 

[ 출처 및 참조 ]

- 부트 캠프 강의를 들은 후 정리한 내용입니다.

- [Do it! 알고리즘 코딩 테스트 - 자바 편]