[백준] 9251, 9252 LCS 1,2

2중 반복문을 돌려서 해당 문자열까지 겹치는 횟수를 2차원 배열에 기록하는 방법으로 문제를 해결했다.

 

여기서 중요한 것은 2차원 배열에 기록을 할 때 문자 하나하나를 비교해서 기록하는 것이 아닌

문자열과 비교해서 기록해야 한다는 것이다.

예를 들어 왼쪽 문자열(ACAYKP)에서 부분 문자열 A와 위쪽 문자열(CAPCAK)에서 부분문자열 C와 비교한다면

A와 C는 겹치는 부분이 없으므로 0이 된다.

 

그다음

왼쪽 문자열(ACAYKP)에서 부분 문자열 AC와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보면

AC와 C는 겹치는 문자가 C 하나가 있다. 따라서 해당 부분에 1을 기록한다.

 

그다음

왼쪽 문자열(ACAYKP)에서 부분 문자열 ACA와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보면

ACA와 C는 겹치는 문자가 C 하나가 있다. 따라서 해당 부분에 1을 기록한다.

이런 식으로 문제를 적어나가면 위와 같은 사진이 나오게 된다.

 

다 적으로 규칙이 보이게 된다.

1. 행(a)과 열(b)이 같게 되는 경우 a-1행 b-1열의 값보다 1이 크다.

2. 1번과 같은 상황이 아닌 경우 (a-1행 b열) or (a행 b-1열) 중 큰 값과 같다.

 

점화식으로 나타내면

1. LCS [a][b] = LCS [a-1][b-1] + 1;

2. LCS [a][b] = max(LCS [a-1][b], LCS [a][b-1]);

 

따라서 배열의 가장 마지막에는 공통적인 문자열의 길이가 적히게 된다.

 

□ 소스코드

void LCS9251(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    string arr1, arr2;
    cin >> arr1 >> arr2;
    
    int LCS[1001][1001] = {0};
    
    for(int i=0;i<=arr1.size();i++){
        for(int j=0;j<=arr2.size();j++){
            if( i==0 || j == 0){
                LCS[i][j] = 0;
            }
            else if( arr1[i-1] == arr2[j-1]){
                LCS[i][j] = LCS[i-1][j-1] + 1;
            }
            else{
                LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
            }
        }
    }
    
    cout<<LCS[arr1.size()][arr2.size()]<<endl;
}

 

가장 긴 수열 시리즈에서도 있다시피 가장 긴 개수만 구하면 뭔가 찜찜해서 어떤 문자열도 있을까 궁금해서 문자열도 구해보았다.

 

LCS 2가 있었네..?

이 부분도 Dp를 역추적하는 방식인데

위 사진에서 보다시피 2차원 배열에서 마지막 부분이 공통부분의 가장 긴 길이가 기록된다. (LCS [arr1.size()] [arr2.size()];)

 

2. LCS[a][b] = max(LCS [a-1][b], LCS [a][b-1]);

2번 점화식을 보면 LCS [a-1][b], LCS [a][b-1] 둘 중 하나의 값이 LCS [a][b]가 된다. 

따라서 반대로 생각하면 해당 점화식을 거꾸로 따라가면 어떤 문자로 구성되어 있는지 확인할 수 있다!!

 

만약 2번 점화식을 거꾸로 따라가다가 더 이상 자신과 같은 게 없는 경우 1번 점화식의 경우를 적용시켜야 한다.

1. LCS [a][b] = LCS [a-1][b-1] + 1;

행과 열을 1씩 거꾸로 올리면 된다.

 

□ 소스코드

stack<char> subSequence;
int arr1Len = arr1.size();
int arr2Len = arr2.size();

while(arr1Len > 0 && arr2Len>0){

    if(LCS[arr1Len][arr2Len] == LCS[arr1Len][arr2Len-1]){
        arr2Len --;
    }
    else if(LCS[arr1Len][arr2Len] == LCS[arr1Len-1][arr2Len]){
        arr1Len --;
    }
    else{
        subSequence.push(arr2[arr2Len-1]);
        arr1Len --;
        arr2Len --;
    }
}



while(!subSequence.empty()){
    cout<<subSequence.top()<<" ";
    subSequence.pop();
}
cout<<endl;

 

연습이 필요할 것 같다.