[C++] BOJ 9251, 1958 : LCS, LCS 3

 

 

 

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

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

 

문제 3줄 요약

1. Longest

2. Common

3. Subsequence

 

---

 

오늘은

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제를 풀어봤다.

 

최장 공통 수열은

문제에도 설명되어있듯이

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것이다.

 

ex) ACAYKP, CAPCAK → LCS : ACAK

 

LCS와 다른게 LIS라는 것도 있던데..

이건 다음에 풀어보자!

 

일단 LCS의 알고리즘 분류가

DP로 되어있다.

 

DP 테이블에 어떤 값을 저장해야하는지

도무지 감이 잡히지 않아서

바로 유튜브 서칭!

 

https://www.youtube.com/watch?v=EAXDUxVYquY

 

한국외대 신찬수 교수님이

30분 정도가량 설명해주시는 것을 듣고

어느 정도 이해하게 되었다..!

 

https://www.youtube.com/watch?v=EAXDUxVYquY

 

특히

좌측의 두 그림에서 확 와닿았다.

 

두 개의 수열을 비교할 때,

X의 i 번째와 Y의 j 번째가 같다면

두 개는 최장 공통 수열에 포함(+1)시키고

 

그 전의 1~(i-1) 까지의 x 값들과

1~(j-1) 까지의 y 값들을 비교한 LCS를 구해주면 되는 것이다.

 

만약 다르다면?

X의 i 번째 또는 Y의 j 번째를 포함하는 수열의 LCS 중 최대값을 선정해주면 되겠다.

 

 

따라서 점화식으로 표현해보면

아래와 같다.

            if(X[i] == Y[i]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

 

 

사실 이 문제의

핵심은 위의 저 코드가 전부다.

 

따라서 문제는 아래와 같이 풀 수 있다.

 

#include <iostream>
#include <string>

using namespace std;

int dp[1001][1001];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    string a, b;
    cin >> a >> b;

    for(int i=1; i<=a.length(); i++)
    {
        for(int j=1; j<=b.length(); j++)
        {
            if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    
    cout << dp[a.length()][b.length()];
    return 0;
}

 

---

 

위 문제와 이어지는 문제 중

LCS 3은 기존에 2개의 수열 비교가 아닌 3개의 수열을 비교하는 것이다.

 

이 경우에는

3개의 수열이 모두 같은 문자를 가르키면 +1,

아닌 경우에는 그 외의 경우의 수 중 가장 큰 값을 넣어주면 되겠다.

 

따라서

아래와 같이 풀 수 있겠다.

 

#include <iostream>
#include <string>

using namespace std;

int dp[101][101][101];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    string a, b, c;
    cin >> a >> b >> c;

    for(int i=1; i<=a.length(); i++)
    {
        for(int j=1; j<=b.length(); j++)
        {
            for(int k=1; k<=c.length(); k++)
            {
                if(a[i-1] == b[j-1] && b[j-1] == c[k-1]) dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                else dp[i][j][k] = max({dp[i][j-1][k-1], dp[i-1][j][k-1], dp[i][j-1][k], dp[i-1][j][k], dp[i][j][k-1], dp[i-1][j-1][k]});
            }
        }
    }

    cout << dp[a.length()][b.length()][c.length()];
    return 0;
}

 

이 문제를 풀면서

c++ 11부터는 max에 리스트 형식으로 불러와

다수의 값을 한번에 비교할 수 있다는 것을 알았다!

 

---

 

오늘은

LCS : 최장 공통 부분 수열을 알아보았다.

다음엔 LIS를 알아보도록 하겠다!