[백준][c++] 9251번, 9252번 LCS 1~2 (최장 공통 부분 수열) (dp)

1. 문제

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

9251번: LCS

 

2. 최적 부분 구조(optimal substructure)

최장 공통 부분 수열에서는

 

시작점이 중요하다

 

다음과 같은 함수를 만들어보자

solve(aidx, bidx) = a 문자열은 aidx 에서 , b문자열은 bidx에서 시작해서 각각 문자열 끝까지                           만들어질 수 잇는 최장 공통 부분 수열의 최대 길이

 

임의의 문자열 a와 b가 있고 이들의 최장 공통 부분 수열 c가 있다고 해보자

 

이때 C의 i번째 문자가 a의 aidx, b의 bidx 의 문자라면

 

a의 aidx에서부터 시작하는 부분문자열과 b의 bidx에서부터 시작하는 부분문자열의

 

최장 공통 부분 수열이 c에서 i에서부터 시작하는 부분문자열이라는 것이다.

 

만약 이 부분문자열보다 긴 최장 공통 부분 수열이 존재한다면 

 

c가 최장 공통 부분 수열이라는 가정이 무너지므로 모순이된다.

(그 수열을 이어 붙여서 더 긴 수열을 만들 수 있기 때문에)

 

 

이러한 사실로부터 우리는 두가지 알 수 있는 점이 있다.

 

부분문제의 최적이 전체문제의 최적이된다는 것과 

 

각 문자열의 시작점과, 최장 공통 부분 수열의 길이는 1 : 1 대응 된다는 점이다.

 

3. 재귀 

부분 문제의 최적이 전체문제의 최적이된다.

 

a와 b의 임의의 인덱스 i, j 는 다음 3가지 부분 문제로 이루어져있다는것을 직관적으로 알 수 있다.

 

1) i + 1 , j            

2) i , j + 1             

3) i + 1, j + 1      : 만약 문자가 같으면, + 1 아니면 + 0 

 

이를 함수식으로 풀어보면 다음과 같다.

solve(aidx, bidx)  = max(solve(aidx + 1, bidx) ,                                  solve(aidx, bidx + 1) ,                                 solve(aidx + 1, bidx + 1) + a[aidx] == b[bidx] )

 

 

4. 코드

1:1 대응이 된다는점에서

 

메모이제이션 기법을 사용할 수 있다.

 

여러 부분문제들이 겹치는 상황이 만들어지는것을

 

점화식에서 충분히 예측할 수 있으므로 

 

이는 수행시간을 많이 줄여줄 것이다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
 
std::string a, b;
int cache[1001][1001];
 
int solve(int aIdx, int bIdx) {
    if(aIdx == a.size() || bIdx == b.size()) {
        return 0;
    }
    int& ret = cache[aIdx][bIdx];
    if(ret != -1) {
        return ret;
    }
    ret = 0;
    
    ret = solve(aIdx + 1, bIdx);
    ret = std::max(ret, solve(aIdx, bIdx + 1));
    ret = std::max(ret, solve(aIdx + 1, bIdx + 1) + (int)(a[aIdx] == b[bIdx]));
    
    return ret;
}
 
int main() {
    std::cin>>a>>b;
    memset(cache, -1, sizeof cache);
    std::cout<<solve(0, 0);
}

 

 

5. 추적하기 (9252번)

실제 답을 내놓는것,

 

각각의 부분문제를 인덱스로 표현하여 (3개의 부분문제를 0~2로 표현)

 

만약 업데이트됬으면 이 부분문제에 해당하는 번호(0~2)를 최대 길이와 같이 저장한다.

 

그리고, 이 저장된 인덱스를 가지고 

 

그대로 다시 한번 재현하면 실제 답을 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
 
using namespace std;
 
std::string a, b;
int cache[1001][1001];
int tracking[1001][1001];
 
int da[3] = {1, 0, 1};
int db[3] = {0, 1, 1};
 
int solve(int aIdx, int bIdx) {
    if(aIdx == a.size() || bIdx == b.size()) {
        return 0;
    }
    int& ret = cache[aIdx][bIdx];
    if(ret != -1) {
        return ret;
    }
    ret = 0;
    for(int i = 0; i < 3; i++) {
        int temp = solve(aIdx + da[i], bIdx + db[i]) + ((i == 2) ? (int)(a[aIdx] == b[bIdx]) : 0);
        if(temp > ret) {
            tracking[aIdx][bIdx]= i;
            ret = temp;
        }
    }
    return ret;
}
void print(int aidx, int bidx) {
    if(aidx == a.length() || bidx == b.length()) return;
    if(a[aidx] == b[bidx] && tracking[aidx][bidx] == 2) {
        std::cout<<a[aidx];
    }
    return print(aidx + da[tracking[aidx][bidx]], bidx + db[tracking[aidx][bidx]]);
}
 
int main() {
    std::cin>>a>>b;
    memset(cache, -1, sizeof cache);
    int len = solve(0, 0);
    std::cout<<len<<"\n";
    if(len != 0) {
        print(0, 0);
    }
}