Dynamic Programming

 

개요

 Dynamic Programming은 흔히 생각하는 동적 프로그래밍(ex 동적 할당)과는 거리가 있다. 따라서 동적 계획법이라고 번역하는 것이 맞다고 한다. 동적 계획법에서는 어떤 문제를 더 작은 문제들로 나누고 각 조각의 답을 계산하고, 이 답들로 원래 문제의 답을 계산한다. 다만 어떤 부분 문제가 여러번 계산이 될 가능성을 없애기 위해 각 문제의 답을 메모리에 저장해 둔다.

가장 대표적인 동적 프로그래밍을 이용가능한 예인 피보자치 수열로 설명한다.

보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.

function fib(n)

 if n = 0 return 0

 else if n=1 return 1

 else return fib(n-1) + fib(n-2)

 

이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

여기서 fib(2) fib(1) 들이 여러번 중복 계산되는 것을 볼 수 있다.

이 fib(1) fib(2)에 해당하는 값들을 미리 배열에 저장해두고 그때그때 꺼내쓰는 방식이다.

 

예제1 와일드카드

https://algospot.com/judge/problem/read/WILDCARD

algospot.com :: WILDCARD

문제

와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.

와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.

예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p* 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다.

와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.

 

출력

각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.

 

예제 입력

2

he?p

3

help

heap

helpp

*p*

3

help

papa

hello

 

예제 출력

heap

help

help

papa

 

문제 요약 : 와일드카드의 ?는 문자 하나랑 매칭되고 *은 0글자 이상의 어떤 문자열에도 대응된다. 패턴에 대응되는 문자열을 찾아라.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    char[] wc;    // 와일드카드 문자열
    char[] fn;    // 파일이름 문자열
    ArrayList<String> fileNameArray;
    
    /* 동적프로그래밍 저장 배열
     * -1 : 계산되지 않음
     *  1 : 일치
     *  0 : 불일치 */
    int[][] cache;
    
    
    Main(String wildCard, ArrayList<String> fileNameArray){
        this.wc = wildCard.toCharArray();
        this.fileNameArray = fileNameArray;
        this.cache = new int[101][101];
    }
    
    public int match(int wIdx, int fnIdx){
        
        // 동적 프로그래밍
        if(cache[wIdx][fnIdx] != -1)
            return cache[wIdx][fnIdx];
        
        // 1:1 대응, 일치하면 인덱스 증가 후 재귀호출
        if(wIdx < wc.length && fnIdx < fn.length)
            if(wc[wIdx] == '?' || wc[wIdx] == fn[fnIdx])
                return cache[wIdx][fnIdx] = match(wIdx+1, fnIdx+1);
        
        // 와일드카드와 파일명 모두 끝에 도달, 파일명도 끝에 도달했어야 일치
        if(wIdx == wc.length)
            return cache[wIdx][fnIdx] = (fnIdx == fn.length)? 1 : 0;

        // * 문자를 만난 경우
        if (wc[wIdx] == '*') {
            if (match(wIdx + 1, fnIdx) == 1 || 
               (fnIdx < fn.length && match(wIdx, fnIdx + 1) == 1))
                return cache[wIdx][fnIdx] = 1;
        }
        
        return cache[wIdx][fnIdx] = 0;
    }
    
    public void solve(){
        
        ArrayList<String> resFileName = new ArrayList<String>();
        for(int i=0; i<fileNameArray.size(); i++){
            
            // 캐쉬 초기화
            for(int[] arr : this.cache)
                Arrays.fill(arr, -1);
            
            String temp = fileNameArray.get(i);
            fn = temp.toCharArray();
            if(match(0,0) == 1)
                resFileName.add(temp);
        }
        
        // 정렬 후 출력
        Collections.sort(resFileName);
        for(String str : resFileName)
            System.out.println(str);
    }
    
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        
        for(int i =0; i<num; i++){
            
            String w = sc.next();
            int file = sc.nextInt();
            
            ArrayList<String> fileNameArray = new ArrayList<String>();
            for(int j=0; j<file; j++)
                fileNameArray.add(sc.next());
            
            Main main = new Main(w, fileNameArray);
            main.solve();
        }
    }
}

예제2 원주율 외우기

https://algospot.com/judge/problem/read/PI

algospot.com :: PI

문제

(주의: 이 문제는 TopCoder 의 번역 문제입니다.)

가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

1. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
2. 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
3. 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
4. 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
5. 그 외의 경우 난이도: 10

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.

 

출력

각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.

 

예제 입력

5

12341234

11111222

12122222

22222222

12673939

 

예제 출력

4

2

5

2

14

 

 

문제 요약 : 숫자를 끊어서 외우고 싶어하는데 각각의 난이도는

1. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
2. 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
3. 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
4. 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
5. 그 외의 경우 난이도: 10

일때 최소의 난이도를 계산하라.

예제입력인 12341234 = {1234,1234}로 11111222 = {11111,222}로 나뉜다.

memorize(begin) = Min(memorize(begin+L) + classify(N[begin, L] ) )
( 3<=L <= 5 )

import java.util.Arrays;
import java.util.Scanner;

public class PI {
    static final int INF = 987654321;
    static int[] cache = new int[10002];
    static String N;

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

        int C = Integer.parseInt(sc.next());
        while (C-- > 0) {
            N = sc.next();
            Arrays.fill(cache, -1);

            int res = memorize(0);
            System.out.println(res);
        }
        sc.close();
    }

    // 수열 N[begin]을 외우는 방법 중 난이도의 최소합을 리턴
    static int memorize(int begin) {
        //System.out.println("Memorize " + N.substring(begin));
        // base case : 수열 끝에 도달한 경우 0리턴
        if (begin == N.length())
            return 0;

        if (cache[begin] != -1)
            return cache[begin];

        cache[begin] = INF;
        for (int L = 3; L <= 5; ++L) {
            //System.out.println("L " + L);
            if (begin + L <= N.length())
                cache[begin] = Math.min(cache[begin], memorize(begin + L) + classify(begin, begin + L - 1));
        }

        return cache[begin];
    }

    // 각 부분 문자열의 난이도를 리턴
    static int classify(int a, int b) {
        int len = b - a + 1;
        String M = N.substring(a, a + len);
        //System.out.println("classfiy " + M);
        char[] C = M.toCharArray();

        // 난이도 1인가? 2222, 444, 55555
        if (isSameChar(C))
            return 1;

        // 난이도 2인가? 등차수열인지 검사하고 공차가 1혹은 -1 : 숫자가 1씩 단조 증가/감소 1234 or 3210
        boolean progressive = true;
        for (int i = 0; i < M.length() - 1; i++) {
            if (C[i + 1] - C[i] != C[1] - C[0]) { // 등차수열인가?
                progressive = false;
                break;
            }
        }
        // 공차가 1 혹은 -1 인가?
        if (progressive && Math.abs(C[1] - C[0]) == 1)
            return 2; // 공차가 1인 등차수열
        if (progressive)
            return 5;// 공차가 1이 아닌 등차 수열은 난이도 5

        boolean alternating = true;
        for (int i = 0; i < M.length(); i++) {
            if (C[i] != C[i % 2]) {
                alternating = false;
                break;
            }
        }
        if (alternating)
            return 4; // 두수가 번갈아 나오는 경우

        return 10; // 해당하는 경우가 없다면 난이도 10
    }

    static boolean isSameChar(char[] ch) {
        for (char c : ch)
            if (ch[0] != c)
                return false;

        return true;
    }
}

 

예제3 계단 오르기

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

2579번: 계단 오르기

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6 10 20 15 25 10 20

예제 출력 1 복사

75

 

해결법 : 첫번째로 현재 있는 계단 전의 계단을 밟지 않는 경우와 현재 있는 계단 전의 계단을 밟은 경우 이렇게 두가지로 나올 수 있다.

(CASE 1 ) 현재 계단(N)에서 얻을 수 있는 최대 점수 = 현재 계단(N) 점수 + 두 칸 전 계단(N-2)에서 얻을 수 있는 최대 점수

(CASE 2) 현재 계단(N)에서 얻을 수 있는 최대 점수 = 현재 계단(N) 점수 + 한 칸 전 계단(N-1)에서 얻을 수 있는 점수 + 세 칸 전 계단(N-3)에서 얻을 수 있는 최대 점수

 

import java.util.Scanner;

public class Test{
    public static int max(int a, int b)
    {
        return a > b ? a : b;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
       int N = sc.nextInt();
       int[] stair = new int[305];
       int[] cache = new int[305];
       for (int i = 1; i <= N; i++)
        stair[i] = sc.nextInt();
        for (int i = 1; i <= 3 && i <= N; i++){
            if (i!=3)
                cache[i] = cache[i - 1] + stair[i];
            else
                cache[i] = max(stair[i] + cache[i - 2], stair[i] + stair[i - 1]);
        }
            
        for (int i = 4; i <= N; i++)
            cache[i]=max(stair[i] + cache[i - 2], stair[i] + stair[i - 1] + cache[i - 3]);
        System.out.printf("%d\n",cache[N]);
    }
    
}​