백준 9251 LCS

추석 연휴 끝나고 DP를 해보려고 잡은 문제이다. DP의 개념은 살짝 알고 있고, 관련 문제도 몇 번 푼 적이 있지만 제대로 좀 훑고 싶었다. Dynamic Programming은 문제를 푸는 과정에서 계속 부분부분 정답을 기록해가며 문제에 대한 해답을 풀어가는 방식이라고 생각한다. 근데 이게 나중에 보고 나면 아...~ 하는데 접근하기가 너무 어려운 것 같다.

 

이번 문제는 두 문자열이 있고, 그 문자열들의 부분 수열 중 가장 긴 공통 부분 수열의 길이를 찾는 문제이다.

처음 DP 쓰고 어 문자열~ 하고 접근했을 때, 1차원 배열을 선언해서, 먼저 받은 문자열을 쭉 스캔하면서 거기 기준으로 다른 문자열 어떤 위치까지 만들 수 있는가를 저장하는 방식으로 작성했다. 근데 아무리 생각해도 그렇게 접근하게 되면 "부분 수열"이라는 관점에서 맞게 하기 어려워 보였다.

 

어차피 첫 DP 문제었기도 했고, 좀 검색을 해봤다. 솔루션들은 왠만하면 다 2차원 배열을 사용하고 있었다. 두 문자열의 길이만큼의 2차원 배열(첫 문자열 * 두번째 문자열)을 만들어 두고, 각 셀은 행에서 현재까지 나온 문자열과 열에서 현재까지 나온 문자열 사이 LCS 길이를 저장하게 된다.

처음 배열은 0으로 초기화를 한다. 그리고 행과 열의 문자를 비교하면서 표를 채운다.

두 문자가 같으면 현재 위치 값은 왼쪽 대각선 값 + 1 이고,

두 문자가 다르면 현재 위치 값은 max(왼쪽 값, 위쪽 값) 이다.

	A	C	A	Y	K	P
C	0
A
P
C
A
K

만약 배열 범위를 벗어난 값을 봐야 할 경우, 0으로 가정한다. 해당 과정을 사용해 표를 채우면,

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A
P
C
A
K

양 쪽이 C 일때 1로 바뀌고, 나머지 셀들은 max(1, 0) 값인 1을 가지게 된다.

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

셀을 전부 채우고 값의 의미를 다시 보면, 표시된 3은 "ACAYK"와 "CAPCA"까지의 LCS길이를 의미한다. "ACA"의 3이 딱 맞다.

이제 우리는 해당 배열의 마지막 값을 확인하면 우리가 찾던 LCS 길이를 찾아낼 수 있다.

---

#include <iostream>
#include <string>
#include <vector>

template <typename T>
std::ostream& operator<<(std::ostream &os, std::vector<std::vector<T> > vec)
{
    for (int i = 0; i < vec.size(); i++)
    {
        for (int j = 0; j < vec[0].size(); j++)
            os << vec[i][j] << " ";
        os << '\n';
    }
    return os;
}

int main()
{
    std::string s1;
    std::string s2;
    std::cin >> s1 >> s2;

    std::vector<std::vector<int> > dp(s2.size(), std::vector<int>(s1.size(), 0));

    for (int i = 0; i < s2.size(); i++)
    {
        for (int j = 0; j < s1.size(); j++)
        {
            if(s2[i] == s1[j])
            {
                if(!i || !j)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                if(!i && j)
                    dp[i][j] = dp[i][j - 1];
                else if (i && !j)
                    dp[i][j] = dp[i - 1][j];
                else if (!i && !j)
                    dp[i][j] = 0;
                else
                    dp[i][j] = std::max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    // std::cout << dp;
    std::cout << dp[s2.size() - 1][s1.size() - 1];
    // int dp[s1.size()];
//     memset(dp, 0, sizeof(dp));
// // 섞여있을 때 이렇게 하면 안됨.
//     int s2Idx = 0;
//     if (s1[0] == s2[s2Idx])
//     {
//         dp[0] = 1;
//         s2Idx++;
//     }
//     for(int i = 1; i < s1.size(); i++)
//     {
//         if (s1[i] == s2[s2Idx])
//         {
//                dp[i] = dp[i-1] + 1;
//                s2Idx++;
//         }
//     }
//     std::cout << dp[s1.size() - 1];
}

/*
2D 접근을 많이 해 볼 필요가 있다. 어렵다 DP 접근은. 많이 보는것만이 장땡일듯...
*/

 

코드는 진짜 별거 없다. 인덱스 초과 범위(0 밑) 처리 외에 DP에 값 넣어주는 코드가 다다... DP는 점화식을 찾는게 관건이 되는 문제 유형인 것 같다. 좀 길게 보고 DP를 많이 보려 한다. 근데 또 풀다보면 이게 이렇게풀리네; 하면서 시원하기도 하고.. 허허..

 

오늘도 평온한 하루가 되길. 슨민.