[Baekjoon Online Judge] 백준 9252번 LCS 2(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 9252번 LCS 2

(C++, Python)

(글쓴날 : 2020.04.22)

 

---

* Baekjoon Online Judge, 백준 9252번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 9252번 LCS 2

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/9252

9252번: LCS 2

---

2) 풀이 과정

* 시간 복잡도 : O(nm)

 

최장 공통 부분 수열 LCS(Longest Common Subsequence)를 구하는 문제입니다.

단, 이전 문제는 LCS의 길이만 구했지만, 이번에는 LCS 자체도 구해 출력해야 합니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

먼저, 이전 문제에서 LCS의 길이를 구할 때처럼, 2차원 테이블에 memoization을 해 놓은 뒤 LCS를 구할 수 있는 규칙을 찾아야 합니다.

정해인지는 모르겠지만, 제가 찾은 규칙은 테이블의 마지막 행부터 거꾸로 열을 탐색해가며 수열의 길이와 같은 인덱스 값이 있을 경우, 해당 인덱스의 문자를 스택에 저장하였고, 탐색이 끝난 후, 스택을 출력하여 LCS를 완성해 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int memoization[1001][1001];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    string str1 = "";
    string str2 = "";
    cin >> str1;
    cin >> str2;
    str1 = "0" + str1;
    str2 = "0" + str2;
 
    int N = str2.size();
    int M = str1.size();
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (!i || !j)
                continue;
 
            if (str1[j] == str2[i])
                memoization[i][j] = memoization[i - 1][j - 1] + 1;
            else
            {
                if (memoization[i - 1][j] > memoization[i][j - 1])
                {
                    memoization[i][j] = memoization[i - 1][j];
                    continue;
                }
                memoization[i][j] = memoization[i][j - 1];
            }
        }
    }
 
    int lcsLength = memoization[N - 1][M - 1];
    vector<char> stack;
 
    for (int i = N - 1; i > 0; i--)
    {
        for (int j = 1; j < M; j++)
        {
            if (memoization[i][j] == lcsLength)
            {
                if (str1[j] == str2[i])
                {
                    stack.push_back(str1[j]);
                    lcsLength--;
                    break;
                }
            }
        }
    }
 
    lcsLength = memoization[N - 1][M - 1];
    cout << lcsLength << '\n';
    for (int i = 0; i < lcsLength; i++)
    {
        cout << stack.back();
        stack.pop_back();
    }
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
str1 = "0" + input().rstrip()
str2 = "0" + input().rstrip()
 
N = len(str2)
M = len(str1)
memoization = [[0] * M for _ in range(N)]
 
for i in range(N):
    for j in range(M):
        if not i or not j:
            continue
 
        if str1[j] == str2[i]:
            memoization[i][j] = memoization[i - 1][j - 1] + 1
        else:
            if memoization[i - 1][j] > memoization[i][j - 1]:
                memoization[i][j] = memoization[i - 1][j]
            else:
                memoization[i][j] = memoization[i][j - 1]
 
lcsLength = memoization[-1][-1]
stack = []
 
for i in range(N - 1, 0, -1):
    for j in range(1, M):
        if memoization[i][j] == lcsLength:
            if str1[j] == str2[i]:
                stack.append(str1[j])
                lcsLength -= 1
                break
           
print(memoization[-1][-1])
print(*(stack.pop() for _ in range(len(stack))), sep="")

---