8장. 동적 계획법 (미완성)

본 포스팅은 《구종만, 『알고리즘 문제 해결 전략』, 인사이트》 를 참고하여 만들어졌습니다.

8.1 도입

동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나이다. 동적 계획법(Dynamic Programming)이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(Dynamic), 혹은 프로그래밍(Programing)이란 단어와는 아무런 관련이 없습니다. 따라서 동적 프로그래밍이 아니라 동적 계획법이 적절한 번역이다.

 

중복되는 부분 문제

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있습니다. 그리거 위해서는 각 문제의 답을 메모리에 저장해 둘 필요가 있지요. 이때, 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시(Cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제라고 부릅니다.

 

동적 계획법 알고리즘의 가장 유명한 예 중 하나는 이항계수의 계산입니다. 이항 계수는 다음과 같은 점화식으로 표현 될 수 있고 이를 코드로 작성하면 다음과 같습니다.

이항 계수 점화식

//재귀 호출을 이용한 이항계수의 계산

int bino(int n, int r){
	//base case : n=r, =r0
    if(r==0 || n==r) return 1;
    
    //recursive call
    return bino(n-1,r-1) + bino(n-1,r);
    
  }

 

이 때 bino(4,2)의 호출을 생각해보면 bino(2,1)이 두 번 호출 되는 것을 알 수 있다. bino(2,1)을 계산하기 위해선 bino(1,0)과 bino(1,1)을 재귀호출 하기 때문에 이 계산도 각각 두 번씩 이루어 지게 된다. 즉, 몇몇 부분 문제들을 여러 번 계산하게 되는 비효율이 발생한다! 이러한 비효율은 n과 r이 커짐에 따라 기하급수적으로 증가한다.

이러한 중복 계산을 피하기 위해서는 각 n,r 조합에 대하여 답을 저장하는 캐시 배열을 만들어서 각 입력에 대한 반환 값으로 저장해놓으면 된다! 함수는 매번 호출될 때마다 이 배열에 접근해 값이 저장되어 있는지를 확인한 뒤 저장되어 있다면 이것을 즉시 반환하여 중복계산을 피할 수 있게 된다. 이와 같이 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션(memoization)이라고 부릅니다.

 

//메모이제이션을 이용한 이항 계수의 계산

//Cache를 -1로 초기화 해둔다.
int cache[30][30];

int bino2(int n, int r) {
	//base case 
	if (r == 0 || n == r) return 1;

	//-1이 아니라면 한 번 계산했던 값을 곧장 반환
	if (cache[n][r] != -1) return cache[n][r];

	//직접 계산하여 cache에 저장한 뒤 반환
	return cache[n][r] = bino2(n - 1, r - 1) + bino2(n - 1, r);
}

 

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

수학에서와 달리 프로그래밍에서는 같은 함수의 호출이 다른 결과를 반환 할 수도 있다. 함수의 입력 외에서 함수의 계산에 영향을 주는 전역 변수, 입력 파일, 클래스의 맴버 변수 등이 있기 때문이다. 함수의 반환 값이 오로지 그 입력 값만으로 결정되는지의 여부를 참조적 투명성(referential transparency)이라고 부릅니다. 입력이 고정되어 있을 때 그 결과가 항상 같은 함수들을 참조적 투명 함수라고 부르고, 당연하게도 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다!

 

메모이제이션 구현 패턴

• 항상 base case를 제일 먼저 처리합니다. 입력 범위가 벗어나는 등의 error case도 기저 사례로 처리하면 유용하다. 기저 사례를 먼저 확인하지 않고 cache[ ] 에 접근하면 범위를 벗어나는 등의 오류가 생길 수도 있다.
• 함수의 반환값이 0 이상(혹은 특정 범위)라는 점을 이용하여 cache를 모두 -1(혹은 특정 범위에서 벗어난 값)으로 초기화
• ret을 cache[a][b]에 대한 참조형이라는 데 유의하자. 참조형 ret의 값을 바꾸면 cache[a][b]의 값도 바뀌기 때문에 실수의 가능성을 줄일 수 있다.
• 또 하나 눈여겨볼 것은 memset( )을 이용해 cache를 초기화 시키는 부분이다. 메모이제이션에서는 cache를 초기화 하는 것이 자주 등장한다. 이때 memset( )에 대하여 정확하게 이해하고 사용하는 것이 중요하다. memset( )은 두번 째 인자로 주어진 값을 주어진 모든 바이트에 채우게 된다. 만약 배열이 32bit or 64bit 정수형이라면 정수 배열을 0혹은 -1 바이트로 채운다면 그에 해당하는 정수값도 '운이 좋게' 0 혹은 -1이 된다.

//전부 -1로 초기화해 둔다. 
int cache[2500][2500];

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

    //base case와 error case를 처리
    if(base case) return ...;
    
    //(a,b)에 대한 답을 구한 적이 있으면 곧장 반환
    if(cache[a][b] != -1) return cache[a][b];
    
    //ret을 참조형으로 선언
    int& ret=cache[a][b];
    
    //계산
    ....
    
    return ret;
}

int main(void){

    //memset()을 이용해 cache배열을 초기화
    memset(cache, -1, sizeof(cache));
    
    ...
    
 }

 

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

메모이제이션의 시간 복잡도를 분석하는 과정은 각 입력에 대한 함수를 처음으로 호출할 때와 다름으로 호출할 때 걸리는 시간이 다르기 때문에 어렵게 느껴질 수 있다. 하지만 메모이제이션을 사용하는 알고리즘의 시간 복잡도를 굉장히 간단하게 계산할 수 있는 방법이 있다.

 

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

 

이미 한 번 호출 된 부분 문제는 그 다음에 호출 될 때 cache를 참조하여 값을 반환하기 때문에 시간복잡도에 영향을 주지 않는다. 즉, 시간복잡도에 영향을 주는 함수 호출은 각 부분문제들의 첫 번째 호출임을 알 수 있다. 따라서 존재하는 부분 문제의 수에 각 부분 문제에서 소요되는 시간 복잡도를 곱해주게 된다면 전체 시간 복잡도를 구할 수 있게 된다.

물론 이 식은 수행 시간의 상한을 간단히 계산할 수 있는 방법일 뿐이며, 부분문제가 될 수록 입력의 크기가 작아지는 경우라면 실제 수행 시간은 이 식보다 훨씬 작아질 수도 있다.

 

---

예제 : 외발 뛰기

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

algospot.com :: JUMPGAME

재귀 호출에서 시작하기

동적 계획법 알고리즘을 만드는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것이다. 

 

// 외발 뛰기 문제를 해결하는 재귀 호출 알고리즘

int n, board[100][100];

bool jump(int y, int x){

	//base case : 게임판을 벗어나는 경우
    if(y>=n || x>=n) return false;
    
    //Goal!
    if(y==n-1 && x==n-1) return true;
    
    int jumpSize=board[y][x];
    
    return (jump(y+jumpSize,x) || jump(y,x+jumpSize));
}

 

메모이제이션 적용하기

"원하는 답이 존재하는가?"라는 질문을 완전 탐색으로 구할 때 흔히 가장 문제가 되는 것은 원하는 답은 없는데 전체 답의 개수는 무지막지하게 많은 경우입니다. 이 문제의 경우 완전 탐색을 하기 위해선 n에 대하여 지수적으로 늘어남으로 n=100이면 제한 시간이 초과하게 됩니다.

이 문제에서 주목할 것은 완전 탐색이 만드는 경로의 수는 엄청나게 많지만 jump( )에 주어지는 입력의 개수는 100 x 100 = 100,000개뿐이라는 사실입니다. 또한, jump( )는 참조적으로 투명 함수이기 때문에 메모이제이션을 적용해서 중복된 연산을 없앨 수 있습니다.

 

//메모이제이션을 이용한 JUMPGAME 알고리즘 개선

int n,board[100][100];
int cache[100][100];

int jump2(int y, int x){
	//base case 
    if(y>=n || x>=n) return 0;
    if(y==n-1 && x==n-1) return 1;
    
    //메모이제이션
    int& ret = cache[y][x];
    if(ret!=-1) return ret;
    
    int jumpSize = board[y][x];
    return ret = (jump2(y+jumpSize,x) || jump(y,x+jumpSize));
}

Tip 다른 해법 : 이 문제는 사실 그래프로 모델링해보면 아주 간단한 도달 가능성 문제가 됩니다!

---

동적 계획법 레시피

동적 계획법 알고리즘의 구현은 다음과 같은 두 단계로 이루어집니다.

1. 주어진 문제를 완전 탐색을 이용해 해결합니다.
2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용합니다.

다른 구현 방법에 관하여

물론 재귀 호출을 이용하지 않고도 동적 계획법 알고리즘을 구현할 수 있습니다. 이런 방법을 반복적 동적 계획법이라고 부릅니다. 반복적 동적 계획법에도 많은 장점이 있지만, 모메이제이션을 통한 접근이 좀더 직관적이기 때문에 이 장에서는 기본적으로 모든 동적 계획법 알고리즘을 재귀 호출을 통해 구현합니다.

 

---

8.2 문제 : 와일드카드

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

algospot.com :: WILDCARD

*가 문제로다

이 문제를 어렵게 만드는 것은 *가 몇 글자에 대응되어야 하는지를 미리 알 수 없다는 점이다. 단순하게는 * 다음에 출현하는 글자가 나올 때까지 대응시킬 수 있습니다만 이래서 입력의 세번째 예제를 제대로 해결할 수 없지요. 이럴 때 우리가 할 수 있는 가장 쉬운 방법은 역시 완전 탐색입니다.

주어진 패턴이 m개의 *를 포함한다고 합니다. 이 패턴이 *가 나타날 때마다 쪼개면 이 패턴이 문자열에 대응되는지 확인하는 문제를 m+1조각으로 나눌 수 있습니다. 완전 탐색 함수는 이 문자열 중 모두 몇 글자가 첫 번째 고작에 대응될지를 찾아내기 위해 모든 경우의 수를 다 시도해 봅니다.

물론 실제로 패턴을 직접 쪼깨지 않고도 이를 구현할 수 있습니다. 와일드 카드 w가 원문 s에 대응되는지 여부를 반환하는 함수 match(w,s)를 만들어 봅시다. w와 s를 앞에서부터 한 글자씩 대응해 나가며 , *를 만나거나 둘 중 한 문자열이 끝날 때에 멈춥니다. 이 함수의 첫 부분은 다음과 같을 겁니다.

 

bool match(const string& w, const string& s){
    //w[pos]와 s[pos]를 맞춰나간다.
    int pos=0;
    
    while(pos<s.size() && pos<w.size() && (w[pos] == '?' || w[pos] == s[pos]))
    	pos++;
        
    ....
}

while문은 w와 s를 더이상 맞춰 나갈 수 없을 때 종료합니다. 종료하는 경우의 수를 좀더 자세히 따져 봅시다.

 

1. s[pos]와 w[pos]가 대응되지 않는다.
2. w 끝에 도달했다 : 패턴에 *이 하나도 없는 경우
3. s 끝에 도달했다 : 패턴은 남아있지만 문자열이 이미 끝나버린 경우, 남은 패턴이 모두 *이 아닌 경우를 제외하고 거짓이 된다.
4. w[pos]가 *인 경우 : *가 몇글자에 대응될지 모르기 때문에, 0 글자부터 남은 문자열의 길이까지를 순회하며 모든 가능성을 검사합니다. 이때 w의 pos+1이후를 패턴 w'으로 하고, s의 pos+skip 이후를 문자열 s'로 해서 match(w',s')로 재귀 호출했을 때 답이 하나라도 참이면 답은 참이 된다.

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

 

중복되는 부분 문제

이 알고리즘은 일부 예제 입력의 경우에는 너무 오랜 시간이 걸릴 수 있다는 문제가 있다. 완전 탐색은 각 *에 대응되는 글자 수의 모든 조합을 검사하는데, 문자열이 길고 *가 많을 수록 이 경우의 수는 늘어난다. 만약 이 많은 경우의 수 중 답이 하나도 없다면 우리는 그 답들을 하나하나 다 만들기 전에는 절대 종료하지 않을 것입니다.

패턴 ******a와 원문 aaaaaaaaab 같은 경우가 이런 입력의 종은 예이다. 이 코드가 실행되는 과정에서 수행하는 계산의 대부분이 여러 번 중복으로 이루어지기 때문에 입력이 주어졌을 때 답을 저장하는 cache를 이용하여 프로그램을 훨씬 빠르게 할 수 있을 것이다.

cache를 구현할 수 있는 중요한 단서는 입력으로 주어질 수 있는 w와 s의 종류는 제한되어있다는 것입니다. 재귀 호출할 때 우리는 항장 w와 s의 앞에서만 글자들을 떼내기 때문에 w와 s는 항상 입력에 주어진 패턴 W와 피알명 S의 접미사(suffix)가 됩니다. 따라서 입력으로 주어질 수 있는 w와 s는 각각 최대 101개((문자열의 길이가 100이기 때문에))밖에 없습니다.  이때, match( )가 101 x 101번 이상 호출되었다면 어떤 부분 문제가 반드시 여러 번 계산되고 있다는 뜻이다! 즉 101 x 101 크기의 cache를 이용하여 메모이제이션을 사용 할 수 있게 되는 것이다!

 

//와일드카드 문제를 해결하는 동적 계획법 알고리즘

// -1은 아직 답이 계산되지 않았음을 의미한다.
// 1은 해당 입력들이 서로 대응됨을 의미한다.
// 0은 해당 입력들이 서로 대응되지 않음을 의미한다.
int cache[101][101];

//패턴과 문자열
string W, S;

//와일드카드 패턴 W[w...]가 문자열 S[s...]에 대응되는지 여부를 반환한다.
bool matchMemoized(int w, int s){
	//메모이제이션
    int& ret = cache[w][s];
    if(ret != -1) return ret;
    
    //W[w]와 S[s]를 맞춰 나간다.
    while(s < S.size() && w < W.size( ) && (W[w] == '?' || W[w] == S[s]){
    	w++;
        s++;
    }
    
    //더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
    //2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 참
    if(w==W.size()) return ret = (s==S.size());
    
    //4. *를 만나서 끝난 경우 : *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인
    if(W[w] == '*'){
    	for(int skip=0; s+skip <= S.size() ; skip++)
        	if(matchMemoized(w+1, s+skip))
            	return ret=1;
    }
    
    //3. 이 외의 경우에는 모두 대응되지 않는다.
    return ret=0;
}

 

---

8.3 전통적인 최적화 문제들

동적 계획법의 가장 일반적인 사용처는 최적화 문제의 해결이다. 최적화 문제란 여러 개의 가능한 답 중 가장 좋은 답을 찾아내는 문제를 말한다. 최적화 문제를 동적 계획법으로 푸는 것 또한 완전 탐색에서 시작합니다만, 최적화 문제에 특정 성질이 성립할 경우에는 단순히 메모이제이션을 적용하기보다 좀더 효율적으로 동적 계획법을 구현할 수 있다. 이 성질들이 성립하는 몇 가지 예제 문제들을 살펴보자.

 

---

예제 : 삼각형 위의 최대 경로

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

algospot.com :: TRIANGLEPATH

간단한 예제 문제를 통해 동적 계획법 알고리즘을 설계하는 과정을 살펴보자. 

 

완전 탐색으로 시작하기

가장 먼저 완전 탐색을 통해 이 문제를 해결해 봅시다. 경로를 각 가로줄로 조각 낸 뒤, 각 조각에서는 아래로 내려갈지 오른쪽으로 내려갈지를 선택하면서 모든 경로를 만들기로 합니다. 이때 재귀 호출 함수에는 현재 위치와 지금까지 만난 숫자들의 합을 전달하도록 하자. 그러면 다음과 같은 부분 문제를 얻을 수 있다.

 

pathSum(y, x, sum) = 현재 위치가 (y, x)이고 지금까지 만난 수의 합이 sum일 때, 이 경로를 맨 아래줄까지 연장해서 얻을 수 있는 최대 합을 반환한다.

이때 아래쪽으로 내려갔을 때와 오른쪽으로 내려갔을 때의 최대 합을 각각 path( )를 이용해 표현하면 당므과 같은 점화식을 얻을 수 있다.

 

path1(y, x, sum) = max ( path(y+1 , x, sum+triangle[y][x]) , path(y+1, x+1, sum+triangle[y][x]) )

 

무식하게 메모이제이션 적용하기

앞에서 정의한 점화식은 답을 구하기 위해 모든 경로를 다 만들어 봐야 한다는 심각한 문제가 있습니다. 가로줄이 추가 될 때마다 지수함수적으로 계산량이 증가하게 됨으로 n이 크다면 계산이 불가능한 분량입니다. 이때 메모이제이션을 적용해 보면 어떨까요?

// MAX_NUMBER: 한 칸에 들어갈 숫자의 최대치
int n, triangle[100][100];
int cache[100][100][MAX_NUMBER*100 +1];

// (y,x) 위치까지 내려오기 전에 만난 숫자들의 합이 sum 일 때
// 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로를 반환한다.
int path1(int y, int x, int sum){
	
    //base case
    if(y==n-1) return sum + triangle[y][x];
    
    //메모이제이션
    int& ret = cache[y][x][sum];
    if(ret != -1) return ret;
    
    sum+=triangle[y][x];
    
    return ret = max(path1(y+1, x+1, sum), path1(y+1, x, sum));
}

완전 탐색에서 구한 알고리즘에 메모이제이션을 적용한 코드입니다. 이 코드는 멀쩡해 보이지만 중대한 결함을 가지고 있습니다. 첫 번째 문제는 사용해야 하는 메모리가 너무 크다는 것입니다. 또 다른 문제는 path1( )이 특정 입력에 대해서는 완전 탐색처럼 동작한다는 것이다. 경로마다 합이 항상 다른경우 같은 계산을 두 번 할 일이 없어지고 완전 탐색과 다를 바가 없어진다.

 

입력 걸러내기

이 알고리즘을 더 빠르게 하는 힌트는 재귀 함수의 입력을 다음과 같이 두 분류로 나눠 보면 얻을 수 있다.

 

1. y와 x는 재귀 호출이 풀어야 할 부분 문제를 지정한다. 이 두 입력이 정해지면 앞으로 우리가 만들 수 있는 경로들이 정해진다. 따라서 이들은 앞으로 풀어야 할 조각들에 대한 정보를 주는 입력이다.
2. 반면 sum은 지금까지 어떤 경로로 이 부분 문제에 도달했는지를 나타낸다. sum은 지금까지 풀었던 조각들에 대한 정보를 주는 입력이다.

이때 과연 sum이 앞으로 남은 조각들을 푸는데 필요할까요? (y, x)에서 맨 아래줄까지 내려가는 최대 경로는 sum이 얼마건 상관 없이 똑같습니다. 단 재귀 함수에서 sum을 입력으로 받지 않으면, 이전가지 어떤 숫자를 만났는지 알 수 없기 때문에 전체 경로의 최대 합을 반환할 수가 없다. 따라서 함수의 반환 값을 전체 경로의 최대치가 아니라 (y, x)에서 시작하는 부분 경로의 최대치로 바꿀 필요가 있다.

 

path2(y ,x) = (y, x)에서 시작해서 맨 나래줄까지 내려가는 부분 경로의 최대합을 반환한다.

 

int n, triangle[100][100];
int cache2[100][100];

// (y, x)위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합을 반환한다.
int path2(int y, int x){

	//base cace
    if(y==n-1) return triangle[y][x];
    
    //메모이제이션
    int& ret = cache2[y][x];
    if(ret != -1) return ret;
    
    return ret = max(path2(y+1,x) , path2(y+1, x+1)) + triangle[y][x];

}

---

이론적 배경 : 최적 부분 구조

위 문제를 해결하는데 가장 중요한 생각은 sum이라는 정보가 다름 경로를 정하는데 아무 상관이 없다는 사실이다. 다시 말해 지금까지 어떤 경로로 이 부분 문제에 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관 없다. 이것은 효율적인 동적 계획법 알고리즘을 적용하기 위해 아주 중요한 조건이다. 이를 최적 부분 구조(Optimal Substructure)라고 부르며 동적 계획법의 중요한 요소로 꼽힌다. 최적 부분 구조는 어떤 문제와 분할 방식에 성립하는 조건입니다. 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 이 조건이 성립한다고 한다. 최단 경로를 찾는 문제는 이렇게 각 부분의 최적해가 전체의 최적해로 이어지기 때문에 최적 부분 구조를 갖는다고 할 수 있습니다.

 

---

예제 : 최대 증가 부분 수열

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

algospot.com :: LIS

완전 탐색에서 시작하기

최대 증가 부분 수열을 찾는 문제를 숫자 하나씩으로 조각 낸 뒤, 한 조걱에서 숫자 하나씩을 선텍하는 완전 탐색 알고리즘을 만들어 보자. 수열 A를 입력받아 LIS의 길이를 반환하는 재귀함수 lis(A)는  A의 모든 중가 부분 수열을 만든 뒤 그중 가장 긴 것의 길이를 반환합니다.

lis(A)가 수열의 첫 숫자로 A[j]를 골랐다고 합시다. A[j]에서 시작하는 증가 수열 중 가장 긴 증가 수열을 찾으려고 한다면 어떻게 해야할까? A[j+1...] 부분 수열에서 A[j]보다 큰 숫자들만 고른 부분 수열 B를 만들고 B의 LIS를 재귀 호출로 계산합니다. B의 LIS를 구할 때 A[j]나 그 이전에 선택한 숫자들은 알 필요가 없죠. 이것은 LIS 문제에도 최적 부분 구조가 성립함을 보여줍니다.

 

int lis(const vector<int>& A){

	//base case : A is empty
    if(A.empty()) return 0;
    
    int ret=0;
    for(int i=0; i < A.size(); i++){
    	vector<int> B;
    	for(int j= i+1; j < A.size(); j++){
        	if(A[i] < A[j]) B.push_back(A[j]);
        }
        
        ret = max(ret, 1+lis(B));
    }
    
    return ret;
}

 

입력 손보기

이 코드는 완전 탐색의 기능은 훌륭히 수행합니다만, 메모이제이션을 적용하기 까다롭다. 우선, 입력이 정수가 아니라 정수의 배열이기 때문이다. A의 정의를 이용해 A를 좀더 간단하게 표현하는 방법을 생각해 봅시다. A는 항상 다음 두 가지 중 하나가 된다.

1. 원래 주어진 수열 S
2. 원래 주어진 수열의 원소 S[i]에 대해, S[i+1...] 부분 수열에서 S[i]보다 큰 수들만을 포함하는 부분 수열

2번 정의에서 이전에 선택한 수들이 정의에 포함되지 않은 데 유념하자! 이전에 선택된 수들은 어차피 마지막에 선택된 수보다 전에 있고 더 작기 때문에, 이들보다 뒤에 있고 커야 한다는 조건은 2번 조건만으로 모두 만족된다. 또한 이 정의에서 유념해 볼 것은 2번 정의에 포함되는 A는 S의 인덱스와 1 : 1 대응 된다는 점이다. A로 주어질 수 있는 입력은 전부 N+1가지 뿐이 없다! 배열을 전역변수로 선언하고(혹은 포인터로 넘겨주고) 시작 위치만을 입력으로 받는 새로운 함수를 생각해 볼 수 있을 것이다.

 

lis(start) = S[start] 에서 시작하는 부분 증가 수열 중 최대의 길이

 

재귀 호출할 때마다 우리는 S[start]보다 뒤에 있고 큰 수들 중 하나를 다음 숫자로 결정한 뒤, 여기서 시작하는 부분 증가 수열의 최대치를 구하게 된다.

int n;

int cache[100], S[100];



//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.

int lis2(int start){



    int& ret=cache[start];

    if(ret != -1) return ret;

    

    //항상 S[start]는 있기 때문이 길이는 최하 1

    ret=1;

    

    for(int next = start +1; next < n ; next++){

     if(S[start] < S[next])

         ret = max (ret, lis2(next) + 1);

    }

    

    return ret;

    

}

 

Tip 별도의 base case가 없기 때문에 for문이 끝나야 끝이 난다!

 

시작 위치 고정하기

lis2( )를 호출할 때는 항상 증가 부분 수열의 시작 위치를 지정해 줘야 하므로, 처음에 호출할 때 각 위치를 순회하면서 최대 값을 찾는 다음과 같은 형태의 코드를 작성해야 합니다.

int maxLen = 0;

for(int begin=0; begin < n; begin++)

 maxLen = max(maxLen, lis2(begin));

이것도 귀찮게 느껴진다면 간단한 문제 변형을 통해 이 코드를 없앨 수 있습니다. S[-1] = -INF라고 가정하는 코드를 작성합니다. lis2(-1)을 호출하면 항상 -INF부터 시작하니까 모든 시작 위치를 자동으로 시도하게 됩니다.

 

int n;

int cache[101], S[100];



//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.

int lis3(int start){

	

    int& ret = cache[start+1];

    if(ret != -1) return ret;

    

    //항상 S[start]는 있기 때문에 길이는 최하 1

    ret=1;

    for(int next=start+1; next<n; next++){

     if(start==1 || S[start] < S[next])

         ret = max(ret, lis3(next) +1);

    }



    return ret;

}

 

더 빠른 해법

더 빠른 해법을 제공하는 알고리즘은 텅 빈 수열에서 시작해 숫자를 하나씩 추가해 나가며 각 길이를 갖는 증가 수열 중 가장 마지막 수가 작은 것은 무엇인지를 추적합니다.

 

C[i] = 지금까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막 값

 

이 값을 이용하도록 코드를 개선하면 LIS의 길이 K에 대하여 O(nK) 시간에 LIS를 찾을 수 있습니다. 여기서 한발짝 더 나아가 C[ ]가 항상 순증가한다는 사실을 깨닫고 나면, C[ ]에서 이분 검색을 함으로 LIS를 O(nlogK) <= O(nlogn)에 찾는 알고리즘을 만들 수 있습니다.

 

---

최적화 문제 동적 계획 레시피

1. 모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계합니다.
2. 전체 답의 점수를 반환하는 것이 아니라 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿉니다.
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있습니다. 여기서 우리의 목표는 가능한 중복되는 부분 문제를 많이 만드는 것입니다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있지요.
4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 합니다.
5. 메모이제이션을 적용합니다.

---

8.4 문제 : 합친 LIS

algospot.com/judge/problem/read/JLIS

algospot.com :: JLIS

탐욕법으로는 안 된다

이 문제를 보고 대부분의 사람들이 처음 생각하는 것은, 두 수열의 LIS를 각각 찾은 뒤 이들을 합치면 되지 않을까 하는 것입니다. 하지만 다음의 같은 두 수열을 생각해보자. [10 20 30 1 2] [10 2는 지정하지 0 30] 각 수열의 LIS을 구해보면 [10 20 30], [10, 20, 30]이 되는데 이보단 [1 2], [10 20 30]을 선택하는 것이 더 긴 합친 LIS를 만들 수 있다는 걸 알 수 있다.

비슷한 문제를 풀어 본 적이 있군요

우리가 기존에 LIS를 찾는 데 사용했던 알고리즘을 변형해 이 문제를 풀어 봅시다. 이렇게 비슷한 문제들은 비슷한 형태의 부분 문제 정의를 써서 풀 수 있는 경우가 많습니다. lis( ) 문제를 해결하는 함수의 정의는 다음과 같았습니다.

                                lis(start) = S[start]에서 시작하는 최대 증가 부분 수열의 길이

이제 수열이 A, B 두개로 늘었으니 재귀 함수도 두 개의 입력을 받아야겠지요. 다음과 같은 형태의 재귀 함수를 이용해 문제를 풀 수 있는지 생각해 봅시다.

             jlis(indexA, indexB) = A[index A]와 B[index B]에서 시작하는 합친 증가 부분 수열의 최대 길이

 

두 수의 순서는 정하지 않았으니, A[indexA], B[indexB] 중 작은 쪽이 앞에 온다고 합시다. 그러면 이 증가 부분 수열의 다음 글자는 A[indexA+1]이후 혹은 B[indexB+1] 이후의 수열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나가 됩니다. 그리고  A[nextA]를 다음 숫자로 선택했을 경우에 합친 증가 부분 수열의 최대 길이는 1+jlis(nextA, nextB)가 됩니다.

 

const long long NEGINF = numeric_limits<long long>::min();
int n, m, A[100], B[100];
int cache[101][101];

//min(A[indexA],B[indexB]), max(A[indexA],B[indexB])로 시작하는 합친 증가 부분 수열의 최대 길이를 반환한다.
//단 indexA == indexB == -1 혹은 A[indexA] != B[indexB]라고 가정한다.
int jlis(int indexA, int indexB){
	
    //메모이제이션
    int& ret = cache[indexA+1][indexB+1];
    if(ret != -1) return ret;
    
    //A[indexA], B[indexB]가 이미 존재하므로 2개는 항상 있다.
    ret =2;
    long long a = (indexA == -1 ? NEGINF : A[indexA]);
    long long b = (indexB == -1 ? NEGING : B[indexB]);
    long long maxElemnet = max(a,b);
    
    for(int nextA=indexA+1; nextA < n ; nextA++)
    	if(maxElement < A[nextA])
        	ret = max(ret, jlis(nextA,indexB) +1);
            
    for(int nextB=indexB+1; nextB < m; nextB++)
    	if(maxElement < B[nextB])
        	ret = max(ret, jlis(indexA,nextB) + 1);
            
    return ret;
    
}

---

8.5 문제 : 원주율 외우기

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

algospot.com :: PI