DP (dynamic programming) 연습

 

[동적계획법 레시피]

1. 모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전탐색 알고리즘을 설계한다

2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분문제 정의를 바꾼다.

3. 재귀 호출 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. 여기서 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것이다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있다.

4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할수 있도록 한다.

5. 메모이제이션을 적용한다.

 

1장. LIS 문제

1-1. 가장 긴 증가하는 부분 순열

최대 증가 부분 수열(LIS) DP 알고리즘은 아래와 같다.

lis 함수를 각 index 별로 호출하는 과정이 귀찮다면 S[-1]을 만들어서 lis 함수 내부에서 사용하는 방법이 있기는 한데, 그것까진 꼭 지금 사용하지 않아도 될것 같다.

왜냐면 이 알고리즘으로 O(n^2) 이라서 최적이 아니기 때문에, 여기서는 DP 의 기본개념만 잡고가려고 한다.

int n;
int cache[100], S[100]
//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
int lis(int start){
    int& ret = cache[start];
    if(ret!=-1) return ret;

    ret = 1;
    for(int next = start+1; next < n; ++next){
        if(S[start] < S[next]){
            ret = max(ret, lis(next)+1);
        }
    }
    return ret;
}


void main(){
    int maxLen = 0;
    for(int begin=0; begin < n; ++begin){
        maxLen = max(maxLen, lis(begin));
    }
    print(maxLen);
}

[예제]백준 11053 문제

11053번: 가장 긴 증가하는 부분 수열

함수를 따로 안만들고 그냥 반복문 안에서 모든것을 해결하는 방식으로 구현해보았다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];

        dp[0] = 1;
        String line = br.readLine();
        String[] splited = line.split(" ");
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(splited[i]);
        }
        int sol = 1;
        for(int i=1; i<N;i++){
            int max = 1;
            for(int j=0; j<i; j++){
                if(arr[j]<arr[i]){
                    max = Math.max(dp[j]+1, max);
                }
            }
            dp[i] = max;
            sol = Math.max(sol, dp[i]);
        }

        System.out.println(sol);


        br.close();
    }

}

---

2장. 점화식 연습

2-1. 백준 12969번 ABC

https://www.acmicpc.net/problem/12969

12969번: ABC

현재 index에 A/B/C 를 넣어봐서, (A,B) / (A,C) / (B,C) 와 같은 쌍의 갯수 (p)가 K가 되는 경우를 찾아서 출력한다.

지금까지의 A의 갯수와 B의 갯수를 활용해서 p를 구하면 된다.

예를 들어 현재 index에서 C를 넣으면 그 이전에 구해온 A와 B의 갯수의 합만큼 새로운 쌍이 생기게 된다.

 

메모이제이션을 안하면 시간초과가 나기 때문에 꼭 해주어야 함

dp[idx][a][b][p] : 현재 idx 까지 a와 b의 갯수에 따른 쌍의 갯수 p

이렇게 하면 문자열이 다르게 생겼어도 결국 구해지는 쌍의 갯수가 똑같기 때문에 문제가 생기지 않는다.

 

import java.io.*;
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static int N;
    public static int K;
    public static char[] arr;
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new char[N];
        int[][][][]dp = new int[N][N][N][N*(N-1)/2]; //dp[idx][a][b][p]

        K = sc.nextInt();
        
        if(solve(dp, 0,0,0,0)==1){
            for(int i=0; i<N; i++)
                System.out.print(arr[i]);
        }
        else{
            System.out.println("-1");
        }
        sc.close();
    }
    public static int solve(int[][][][] dp, int idx, int a, int b, int p){
        if(idx==N){
            if(p==K) return 1;
            return 0;
        }
        
        if(dp[idx][a][b][p]==1) return 0;
        dp[idx][a][b][p]=1;

        arr[idx]='A';
        if(solve(dp,idx+1,a+1,b,p)==1){
            return 1;
        }

        arr[idx]='B';
        if(solve(dp,idx+1,a,b+1,p+a)==1){
            return 1;
        }

        arr[idx]='C';
        if(solve(dp,idx+1,a,b,p+a+b)==1){
            return 1;
        }

        return 0;

    }
}