190116 동적 계획법

2019-01-16

Algorithm
DP

동적 계획법

중복되는 부분 문제(Overlapping subproblems)

큰 의미에서 분할정복과 같은 접근 방식을 의미

처음 주어진 문제->더 작은 문제들->각 조각의 답 계산->원래 문제의 답 계산

어떤 부분문제는 두개 이상의 문제를 푸는 데 사용할 수 있다

답을 한 번만 계산하고 계산 결과를 재활용함
답을 메모리(캐시)에 저장해 둘 필요가 있다

계산의 중복 횟수는 분할의 깊이가 깊어질수록 지수적으로 증가한다(조합 폭발)-> 동적 계획법

이항계수 계산

동적계획법 알고리즘 중 가장 유명한 예시.

서로 다른 n개의 원소 중 k개의 원소를 순서없이 골라내는 방법의 수를 나타냄.

재귀 호출을 이용하여 이 값을 반환하는 함수 bino(n,k)를 작성

private int bino(int n,int k){
    // 기저 사례: n=k(모든 원소를 다 고르는 경우), k=0(고를 원소가 없는 경우)
    if(k==0||n==k) return 1;
    return bino(n-1,k-1)+bino(n-1,k);
}

수행 시간은 재귀 호출이 몇번 이루어지는지 계산하면 알 수 있다.
- 이항계수의 특성상 같은 값을 두번 이상 계산할 일이 빈번하다.
  - bino(2,1)은 bino(3,1)을 계산하기 위해서도 필요하고, bino(3,2)를 계산하는 데도 필요하다.
함수의 중복 호출은 n과 r이 커질수록 기하급수적으로 증가한다.
- n이 1 증가하면 함수 호출 수는 거의 2배 증가한다.
각 n,k조합에 대해 답을 저장하는 캐시 배열을 생성, 각 입력에 대한 반환값 저장

static int cache[30][30]; // -1로 초기화
private int bino2(int n,int k){
    // 기저 사례
    if(k==0||n==k) return 1;
    // -1이 아니라면 한 번 계산했던 값이니 반환
    if(cache[n][k]!=-1) return cache[n][k];
   	// 직접 계산한 뒤 배열에 저장
    return cache[n][k] = bino2(n-1,k-1)+bino(n-1,k)
}

메모이제이션(memoization)
- 함수의 결과를 저장하는 장소를 마련해 두고, 한번 계산한 값을 저장해 뒀다가 재활용
- 모든 부분 문제가 한 번씩만 계산됨을 보장할 수 있다.
2^n로 증가하던 계산 수가 n^2로 줄어듦.

이와 같이 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장, 속도의 향상을 꾀하는 알고리즘.

메모이제이션을 적용할 수 있는 경우

참조적 투명성: 함수의 반환 값이 그 입력값으로만 결정되는가?

->반환값이 항상 같은 함수는 참조적 투명 함수.

메모이제이션은 참조적 투명 함수의 경우에만 적용 가능하다.

메모이제이션 구현 패턴

한 번 계산하는데 아주 오래 걸리는 참조적 투명 함수

// a와 b는 [0,2500)구간 안의 정수
// 반환 값:항상 int형 범위 안에 들어가는 음이 아닌 정수
private int someObscureFunction(int a,int b);

항상 기저 사례를 가장 먼저 처리한다.
- 입력이 범위를 벗어난 경우
함수의 반환 값이 항상 0이상 -> cache[] 모두 -1로 초기화
- Arrays.fill(cache,-1) 이렇게 채우면 됨!
- 함수의 반환 값이 음수도 가능하다면 이 방법은 X

static int cache[2500][2500]; 
/*
for(int i=0;i<cache.length;i++)
	Arrays.fill(cache[i], -1);
*/
private int someObscureFunction(int a, int b){
    // 기저 사례를 먼저 처리한다
    if(...) return ...;
    // (a,b)에 대해 답을 구한 적이 있다면 return
    if(cache[a][b]!=-1) return cache[a][b];
    // 여기에서 답을 계산한다
    return cache[a][b];
}

메모이제이션의 시간 복잡도 분석

(존재하는 부분 문제의 수)*(한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

위의 bino2(n,k)를 호출할 때 걸리는 시간은

k의 최대값은 n, bino2(n,k)를 계산시 만날 수 있는 부분문제의 수는 최대 O(n^2)
각 부분문제 계산시 걸리는 시간은 반복문이 없으니 O(1) ((상수 시간->알고리즘의 전체 수행 시간에 영향을 미치지 않는다))
위에 따라 bino2(n,k) 계산시 걸리는 시간 복잡도는 O(n^2)*O(1)=O(n^2)

예제: 외발뛰기

n*n크기의 격자판에 1~9까지의 정수를 쓴 게임판
게임판의 왼쪽 위 칸에서 시작해 오른쪽 아래 칸에 도착
각 칸에 적혀있는 숫자만큼 아래나 오른쪽으로 이동할 수 있으며, 게임판의 밖으로 나가서는 안됨.
? 게임판이 주어지면, 시작점에서 끝점으로 도달하는 방법이 있는가?

재귀 호출에서 시작하기
- 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘 만들기
- boolean jump(y,x) = (y,x)에서 맨 마지막 칸까지 도달할 수 있는지 여부를 반환
  - jumpSize = 게임판의 (y,x)위치에 있는 수
  - (아래쪽으로 뛰는 경우): jump(y+jumpSize,x)
  - (오른쪽으로 뛰는 경우): jump(y,x+jumpSize)
  - 위의 두 가지 중 한가지만 성공해도 상관 없음
  - jump(y,x)=jump(y+jumpSize,x) jump(y,x+jumpSize)
```
static int n;
static int board[100][100];
private boolean jump(int y,int x){
    // 기저 사례: 게임판을 벗어난 경우
    if(y>=n || x>=n) return false;
    // 기저 사례: 마지막 칸에 도착한 경우
    if(y==n-1| && x==n-1) return true;
    int jumpSize=board[y][x];
    return jump(y+jumpSize,x)||jump(y,x+jumpSize);
}
```
메모이제이션 적용하기
- 완전 탐색으로 구할 때의 가장 큰 문제: 원하는 답은 없는데 전체 답의 수는 아주 많을 때
- 완전탐색이 만드는 경로의 수는 아주 많으나, 입력은 최대 100*100이 주어지게 된다.
  - 비둘기집 원리에 의해 중복으로 해결되는 부분 문제가 항상 존재한다.
- jump(y,x)는 참조적 투명 함수-> 메모이제이션을 적용하여 중복연산 제거 가능
- int jump2(y,x) = 반환하는 값은 참/거짓 둘 뿐이지만 계산 여부를 판별하기 위해 int형 사용
- ```
static int n;
static int board[100][100];
static int cache[100][100];
/*
for(int i=0;i<n;i++){
	Arrays.fill(cache[i], -1);
}
*/
int jump2(int y,int x){
    // 기저 사례 처리
    if(y>=n || x>=n) return 0;
    if(y==n-1 && x== n-1) return 1;
    // 메모이제이션
    if(cache[y][x]!=-1) return cache[y][x];
        int jumpSize=board[y][x];
    return jump2(y+jumpSize,x)||jump2(y,x+jumpSize);
}
```

예제: 와일드카드

다양한 운영체제에서 파일이름의 일부만으로 파일 이름을 지정하는 방법
와일드카드 패턴: 일반적인 파일명과 비슷하지만 특수 문자(*나 ?)를 포함할 수 있는 문자열
와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교, 모든 글자가 일치하면 ‘‘해당 와일드카드 패턴이 파일명과 대응됨’’
- ? : 어떤 글자와도 대응됨
- *: 0글자 이상의 어떤 글자와도 대응됨
  - ex) he?p : help, heap, ~~helpp~~
  - ex) *p* : help, papa, ~~hello~~
와일드카드 패턴과 함께 파일명의 집합이 주어질 때, 그중 패턴에 대응되는 파일명을 찾아내는 프로그램을 작성하라.

입력 예시

3
he?p
3
help
heap
helpp
*p*
3
help
papa
hello
*bb*
1
babbbc

출력 예시
```
heap
help
help
papa
babbbc
```

재귀 호출

*가 몇 글자에 대응되어야 하는 지 미리 알 수 없기 때문에 어려운 문제!
주어진 패턴이 m개의 *를 포함-> 문제를 m+1조각으로 나눌 수 있음

match(w,s) = w와 s를 한 글자씩 대응시켜 나가며 *를 만나거나 둘 중 한 문자열이 끝나면 멈춤

// 와일드카드 패턴 w가 문자열 s에 대응되는지 여부를 반환
private boolean match(String w, String s){
    // w[pos]와 s[pos]를 맞춰 나간다
    int pos=0;
    while(pos<s.length() && pos<w.length() && (w.charAt(pos).equals('?')||w.charAt(pos).equals(s.charAt(pos))))
        ++pos;
    ..
}

종료하는 경우의 수?
- s[pos]!=w[pos]인 경우
- w 끝에 도달했음
- s 끝에 도달했음((남은 패턴이 모두 “*“인 경우 아래 조건에서 처리함))
- w[pos]==”*'’인 경우

완전히 구현하면?

// 와일드카드 패턴 w가 문자열 s에 대응되는지 여부를 반환
private boolean match(String w, String s){
    // w[pos]와 s[pos]를 맞춰 나간다
    int pos=0;
    while(pos<s.length() && pos<w.length() && (w.charAt(pos).equals('?')||w.charAt(pos).equals(s.charAt(pos))))
        ++pos;
    // 더이상 대응할 수 없으면 while문이 끝났는지 확인한다.
    // 2. 패턴 끝에 도달했음: 문자열도 끝났어야 함
    if(pos==w.size())
        return pos==s.length();
    // 4. '*'를 만나서 끝난 경우: *에 몇 글자를 대응해야 하는지 재귀호출하면서 확인
    if(W[w] == '*')
        for(int skip=0;skip+pos<=s.length(); ++skip)
            if(match(w.substring(pos+1),s.substring(pos+skip)))
                return true;
    // 이 외의 경우에는 모두 대응되지 않는다.
    return false;

완전 탐색은 각 *에 대응되는 글자 수의 모든 조합을 검사한다.
- 문자열이 길고 *의 수가 많을수록 경우의 수가 늘어난다.
- 이 많은 경우의 수 중 정답이 없다면?

메모이제이션

문자열을 재귀 호출로 넘기지 않고, 두 문자열의 시작 위치만을 전달

// -1: 아직 답이 계산되지 않았음
// 1:  해당 입력들이 서로 대응됨
// 0:  해당 입력들이 서로 대응되지 않음
static int cache[101][101];
// 패턴과 문자열
static char[] W,S;
// 와일드카드 패턴 W[w...]가 문자열 S[s...]에 대응되는지 여부를 반환한다.
private boolean matchMemoized(int w, int s){
    // 메모이제이션
    int tmp=cache[w][s];
    if(tmp!=-1) return tmp;
    // W[w]와 S[s]를 맞춰 나간다
    while(s<S.length && w<W.length && (W[w]=='?' || W[w] == S[s])){
        ++w;
        ++s;
    }
    // 더이상 대응이 불가능하면 왜 while문이 끝났는지 확인한다
    // 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 함
    if(w==W.length){
        cache[w][s]=(s==S.size);
        return cache[w][s];
    }
    // 4. *를 만나서 끝난 경우: *에 몇 글자를 대응시킬지 재귀호출하며 확인
    if(W[w] == '*')
        for(int skip=0;skip+s<=S.length;++skip)
            if(matchMemoized(w+1,s+skip));
    			return (cache[w][s]=1);
    // 3. 이 외의 경우에는 모두 대응되지 않는다.
    return cache[w][s]=0;
}

O(n^2)시간 내에 푸는 방법
위에서 O(n^3)이 걸리는 이유 : 내부에서 첫 *를 찾고, *에 몇 글자가 대응되어야 할 지 검사하는 반복문이 존재하기 때문이다

재귀함수 내부에 반복문이 없도록 바꾼다면 O(n^2)안에 문제 풀기 가능

// -1: 아직 답이 계산되지 않았음
// 1:  해당 입력들이 서로 대응됨
// 0:  해당 입력들이 서로 대응되지 않음
static int cache[101][101];
// 패턴과 문자열
static char[] W,S;
// 와일드카드 패턴 W[w...]가 문자열 S[s...]에 대응되는지 여부를 반환한다.
private boolean matchMemoized(int w, int s){
    // 메모이제이션
    int tmp=cache[w][s];
    if(tmp!=-1) return tmp;
    // W[w]와 S[s]를 맞춰 나간다
    while(s<S.length && w<W.length && (W[w]=='?' || W[w] == S[s])){
        return cache[w][s]=matchMemoized(w+1,s+1);
    }
    // 더이상 대응이 불가능하면 왜 while문이 끝났는지 확인한다
    // 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 함
    if(w==W.length){
        cache[w][s]=(s==S.size);
        return cache[w][s];
    }
    // 4. *를 만나서 끝난 경우: *에 몇 글자를 대응시킬지 재귀호출하며 확인
    if(W[w] == '*')
            if(matchMemoized(w+1,s)||(s<S.length && matchMemoized(w,s+1)))
    			return (cache[w][s]=1);
    // 3. 이 외의 경우에는 모두 대응되지 않는다.
    return cache[w][s]=0;
}

 190116 BOJ (2251) 물통 190118 DP (1) N으로 표현 