[백준] 9251번: LCS 풀이 및 해설(C++)

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

9251번: LCS

 

풀이

 

 

문제를 풀기 위해서는 주어진 2개의 문자열 중 하나를 기준으로 잡아 생각해야 한다. 여기서는 그 문자열을 기준문자열, 그렇지 않은 문자열을 비교문자열이라고 하겠다. ACAYKP가 여기서는 기준문자열, CAPCAK가 비교문자열이다.

 

기준문자열의 길이만큼 dp 배열을 만든다. 즉 배열 칸이 의미하는 것은 각 번째의 문자를 말한다.

문자열	A	C	A	Y	K	P
인덱스	0	1	2	3	4	5
값	0	0	0	0	0	0

 

그리고 비교문자열의 맨 앞 글자 기준 문자열에 똑같은 문자가 있는지 비교한다. 만약 있다면 1을 추가한다. 비교 문자열의 첫 문자가 C이니 다음과 같이 변한다.

 

 

문자열	A	C	A	Y	K	P
인덱스	0	1	2	3	4	5
값	0	1	0	0	0	0

 

이제 비교문자열 CAPCAK에서 2번째 글자인 A와 같은 문자가 있는지 비교한다. 만약 인덱스 i에 있다면 이제부터는 dp[i]에 

i>k일때의 dp[k]+1 중 최댓값을 저장한다. 그러면 배열 값은 다음과 같이 변한다.

 

다만 문자열을 비교할때는 ACAYKP순이 아닌 PKYACA 역순으로 일치하는게 있는지 찾아야 한다.

 

그렇지 않으면 , 기준문자열이 A,A,A이고 현재 값은 0,0,0이라고 하자. 이때 비교문자열이 A이면 각 값이 1,1,1이 되어야 하는데 1,2,3이 되어버린다.

 

문자열	A	C	A	Y	K	P
인덱스	0	1	2	3	4	5
값	1	1	2	0	0	0

 

다음 글자인 P 비교시

문자열	A	C	A	Y	K	P
인덱스	0	1	2	3	4	5
값	1	1	2	0	0	3

 

다음 글자인 C 비교시

문자열	A	C	A	Y	K	P
인덱스	0	1	2	3	4	5
값	1	2	2	0	0	3

 

 

다음 글자인 A 비교시

문자열	A	C	A	Y	K	P
인덱스	0	1	2	3	4	5
값	1	2	3	0	0	3

 

 

다음 글자인 K 비교시

문자열	A	C	A	Y	K	P
인덱스	0	1	2	3	4	5
값	1	2	3	0	4	3

 

여기 값중 가장 큰 값인 4를 출력하면 된다.

 

내가 생각했던 코드

#include <iostream>
#include <string>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    fastio;
    string st;
    string cp;
    int maxi=0;
    cin>>st;
    cin>>cp;
    int stlen=st.length();
    int cplen=cp.length();
    int dp[stlen]={0};

    for(int i=0; i<cplen; i++){
        for(int j=stlen-1; j>-1; j--){
            if(cp[i]==st[j]){
                int tempmax=0;
                for(int k=0; k<j ;k++){
                    if(dp[k]>tempmax){
                        tempmax=dp[k];
                    }
                }
                dp[j]=tempmax+1;
                if(maxi<dp[j]){
                    maxi=dp[j];
                }
            }
    }
    }

    cout<<maxi;
    
    return 0;
}

라고 쳤더니, 시간초과가 되었다.

위 풀이는 for문이 3개씩 들어간다. 시간 초과를 막기 위해서는 for문을 하나 줄여야 된다.

어떻게 해야 for문을 줄일 수 있을까?

 

내가썼던 풀이를 다시 장고해보았다.

결국 dp[i]에 i>k일때의 dp[k]+1 중 최댓값을 저장한다면 최종적으로 값을 낼때, dp[n]은 n이 증가함에 따라 항상 오름차순으로 나오는 것과 다름이 없다.

애초에 문자열에 추가적으로 문자가 더 붙어 추가될때 값이 줄어드는 경우의 수는 존재하지 않는다.

 

그럼 배열 dp[n]은 n번째 글자까지의 LCS를 출력하게 하고,

시간 복잡도를 줄이기 위해 배열을 2차원으로 만들면?

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

 

과 같이 나올 것이다.(점화식 중 첫 index에서 error가 나는 것을 막기 위해 첫 행과 첫 열에 0을 넣었다)

 

그럼 이제 표를 보고 역으로 어떤 알고리즘을 도입할지를 생각해보자.

우선 행의 글자와 열의 글자를 비교한다.

 

 

일치하지 않는다면: 일치하지 않는다면 별도로 값을 늘릴 필요는 없다. 즉 이전의 숫자를 뜻하는 위의 열의 숫자를

가져다 쓰면 된다. 다만 한 열 안에서 오름차순을 지켜야 하는데, 앞에서 이미 숫자가 증가했을 수 있기에 위의 열과 왼쪽 열 중 큰 값을 가져다 저장하는 것이다.

즉, 왼쪽 값과 위쪽 값중 큰 것을 저장한다.  (dp[j][i] = max(dp[j-1][i],dp[j][i-1]))

 

 

일치한다면: 값을 1 증가시켜야 한다. 그런데 어느 값을 기준으로 해서 1 증가시키고 저장해야 할까? 

 

문자열 ACAA와 AA를 비교한다고 해보자.

	0	A	C	A	A
0	0	0	0	0	0
A	0	1	1	1	1
A	0	1	1	2	2

다음과 같이 표현될 것이다.

빨간색 글자는 값이 일치한다고 위의열 +1을 하면 안된다는 반례이고

파란색 글자는 값이 일치한다고 왼쪽열 +1을 하면 안된다는 반례이다.

 

즉 위쪽 열과 왼쪽 열 둘다 아니다. 왼쪽 위를 비교해야 한다. 왜 그럴까?

우리가 LCS에서 문자열끼리 일치한다면, 비교하기 전 LCS보다 1 증가할 것이다. 비교하기 전 LCS는 왼쪽 위에 있다.

왼쪽 값과 위쪽 값은 이전에 한쪽 문자에 대한 LCS를 마쳤다. 

 

문자열 둘에서 서로 끝에 같은 문자가 붙으면 LCS는 무조건 +1된다. 

즉 ACA와 A 그리고  ACAA와 AA를 비교하면 LCS가 하나 증가한 것이 되기 때문이다. 이것이 이전 공통수열에서 +1 한것이다.

 

 

 

 

 

해답 코드

#include <iostream>
#include <string>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    fastio;
    string st,cp;
    cin>>st>>cp;
    int stlen=st.length();
    int cplen=cp.length();
    int dp[1001][1001]={0};
    for(int i=1; i<cplen+1; i++){
        for(int j=1; j<stlen+1; j++){
            if(cp[i-1]==st[j-1]){
                if(dp[j-1][i] != dp[j][i-1]){
                     dp[j][i]=max(dp[j-1][i],dp[j][i-1]);
                }
                else{
                    dp[j][i]=dp[j][i-1]+1;
                }
            }
            else{
                dp[j][i]=max(dp[j-1][i],dp[j][i-1]);
            }
    }
    }
    cout<<dp[stlen][cplen];

    return 0;
}

해맸던 부분

위의 풀이처럼, 왼쪽위에서 +1할 생각을 하지 못해 시간이 오래 걸렸다.

 

PLUS

시간복잡도를 줄이기 위해 배열의 차원을 늘릴 수 있다.

일단 표를 먼저 만들고 그 다음 알고리즘 규칙을 찾을 수도 있다.