[백준/C++] LCS 2

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 LCS 문제로 Memoization을 잘 이용해 문제를 풀 수 있다.

 

풀이를 고민하다가 두 문자를 비교해 같은 경우 이전에 구했던 LCS를 이용해 경우를 추가하면 되겠다는 생각이 들었다.

 

그래서 이전의 결과를 이용하기 위해 2차원 배열을 만들고 다음과 같이 정의했다.

 

(DP[i][j] = 1번 문자열의 1~i번 문자와 2번 문자열의 1~j번 문자를 이용해 LCS를 만든 경우의 최대길이)

 

 

이제 정의를 이용해 아래 예시를 따라가 보자.

 

그림에서 빨간 네모가 색칠해진 칸을 DP[i][j]라고 하자.

그러면 이 경우 DP[i][j]의 값은 아래의 3가지 경우 중 최대 값이 된다.

 

1. DP[i-1][j-1]의 값 +1 (i번째 문자와  j번째 문자가 같은 경우 +1이 되기 때문)

2. DP[i-1][j]의 값

3. DP[i][j-1]의 값

 

 

2번과 3번에서 i번째 문자와 j번째 문자가 같은 경우를 고려하지 않는 이유는 정의때문이다.

 

예를 들어 2번 경우를 보면 정의에 의해 1번 문자열의 i번째와 문자와 2번 문자열의 j-1번째까지를 이용해 LCS를 구했다.

위 그림의 파란색, 빨간색의 범위로 구한 LCS가 DP[i][j-1]이 되기 때문에 DP[i][j]는 초록색을 추가한 범위의 LCS다.

결국 j번 문자와 비교할 1번 문자열의 문자가 없기 때문에 2번, 3번 경우는 단순히 최대값만 비교하면 된다. 

 

이제 LCS의 길이를 구했으므로 LCS 문자열을 구해보자.

 

처음에 string으로 LCS 문자열을 저장했는데, string의 덧셈을 하는 부분이 너무 시간이 오래 걸려서 다른 방법으로 바꿨다.

 

변경한 방법은 LCS의 최대 길이가 갱신 될 때 마다 이전 LCS의 마지막 문자의 위치를 기록하는 방법이다. 

 

예시의 문자열을 [ACAYKP, CAPCAK]를 이용해 어떻게 기록하는지 파악해보자.

 

여기서  a : b는 1번 문자열의 a번째 문자와 2번 문자열의 b번째 문자가 같다는 뜻이다.

 

그러므로 마지막 부터 탐색을 시작하면 4, 5 번 문자가 같았다는 사실을 알 수 있으므로, 그 문자를 저장한 뒤 [4][5]위치로 이동한다.

마찬가지로 [4][5]위치에 저장된 값을 확인하면 2번문자와 4번 문자가 같았다는 사실을 알 수 있다.

이후 [2][4]위치로 이동하면 된다.

 

위 과정을 반복하면 ACAK라는 문자열을 얻을 수 있다.

[-1][-1]은 더 이상 같은 문자가 없다는 뜻이므로 탐색을 종료하면 된다.

 

 

 

​

[아이디어 정리]

1. 2차원 DP배열을 만들고 DP[i][j]를 1번 문자열의 1~i번째 문자와 2번 문자열의 1~j번째 문자를 이용해 만든 LCS길이로 정의한다.
2.  i번 문자와 j번 문자가 같은경우 DP[i-1][j-1]+1의 값을 DP[i][j]에 저장하고, 같지 않다면, DP[i][j-1], DP[i-1][j]의 2가지 경우를 비교해 LCS의 길이를 갱신한다.
3. LCS의 길이를 갱신할 때, i번째 문자와 j번째 문자가 같다면 i, j의 값을 현재 위치에 저장한다.
4. 만약 DP[i][j-1], DP[i-1][j]값이 최대값이라면, 마지막으로 같은 문자의 위치를 기록한다.
5. LCS를 전부 구한 뒤, 거꾸로 탐색을 시작해 LCS를 구한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;


string FindAns(vector<vector<pair<int, int>>>& sIdx, int i, int j, string& str2)
{
    string retStr = "";
    pair<int, int> p;
    pair<int, int> np;
    p = sIdx[i][j];
    while (p.first != -1 || p.second != -1)
    {
        retStr = str2[p.second] + retStr;
        p = sIdx[p.first][p.second];
    }

    return retStr;

}


int main()
{
    ios::sync_with_stdio(false);
    string str1, str2;
    cin >> str1 >> str2;
    vector<vector<int>> DP(str1.length() + 1, vector<int>(str2.length() + 1));
    vector<vector<pair<int, int>>> sIdx(str1.length() + 1, vector<pair<int, int>>(str2.length() + 1, make_pair(-1, -1))); //그 전에 공통이 어디 위치에 있는지 저장할 값
    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++)
        {
            DP[i][j] = DP[i - 1][j - 1];
            sIdx[i][j] = sIdx[i - 1][j - 1];
            if (str1[i - 1] == str2[j - 1])
            {
                DP[i][j] += 1;
                sIdx[i][j].first = i - 1, sIdx[i][j].second = j - 1;
            }
            else if (DP[i][j - 1] > DP[i][j])
            {
                DP[i][j] = DP[i][j - 1];
                sIdx[i][j] = sIdx[i][j - 1];
            }
            else if (DP[i - 1][j] > DP[i][j])
            {
                DP[i][j] = DP[i - 1][j];
                sIdx[i][j] = sIdx[i - 1][j];
            }
        }
    }
    cout << DP[str1.length()][str2.length()] << endl;
    cout << FindAns(sIdx, str1.length(), str2.length(), str2);
    return 0;
}

 

---

 

마지막으로 같은 문자의 위치를 기록하는 방법으로 LCS문자열을 찾았는데, 다른 사람의 풀이를 보니 더 간단한 방법이 있었다.

LCS에서 같은 문자열인 경우는 대각선과 길이가 1 차이가 나게 된다. 그러므로 대각선의 길이가 1 차이나는 경우에만 문자를 저장하고, 대각선의 길이가 같다면 위아래로 이동해 LCS 문자열을 찾는 방법이 있었다...

 

어쨋든 다른 방법으로 풀었으니까...

 

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