[C++/Python] 백준 9251 - LCS [Gold5]

출처

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

풀이 전략

'알고리즘및문제해결기법' 수업에서 Dynamic Programming [A.K.A DP]에 대해 배우면서 예시로 배웠던 LCS [Longest Common Sequences, 최장부분공통수열] 알고리즘을 사용하여 문제를 풀 것이다.
이 문제를 풀기 위해서는 점화식을 알아야 하고, 점화식을 잘 모른다면 표를 그릴줄만 알아도 점화식 유도는 충분히 할 수 있을 것이라고 생각한다.

풀이

사실 LCS 알고리즘은 왠만한 코딩테스트 준비용 서적에 거의 다 나와있을 정도로 코딩테스트에도 자주 빈출되고, 그만큼 유명한 알고리즘이기 때문에 점화식을 외워놓는다면 쉽게 풀 수 있을 것이다.

위의 그림에서 표를 해석하면, i=0, j=0인 부분 (파란색 형광펜)은 0으로 놓고 화살표를 통해 DP[i][j]값을 채워 나가는 방법이다. 다만 화살표는 단순히 점화식을 조금 더 가시적으로 이해하기 위한 용도이지 코드에서 쓰이지는 않는다.

• str1과 str2의 부분 문자가 일치하지 않으면 왼쪽 또는 위쪽의 DP 값을 가져오는데, 여기에서는 위쪽에서 값을 가져오는 것으로 통일을 했다.
• str1과 str2의 부분 문자가 일치하는 경우 왼쪽 대각선 위 DP[i-1][j-1]의 값을 가져와 일치하는 count를 1만큼 늘려서 DP[i][j]에 저장한다.

위의 두 가지 방법을 계속 진행시키다 보면 DP[len[str1]][len[str2]]인 부분에 도달을 하게 되는데, 그 위치의 값이 최대로 일치하는 공통 문자열의 길이 즉, LCS의 길이 이므로 그 위치의 DP 값을 출력해주면 된다.

소스 코드

두 가지 버전이 있다. 하나는 C++로 풀이한 버전이고 나머지 하나는 Python으로 풀이한 버전이다.
C++ 풀이의 경우 한창 알고리즘 수업에서 LCS에 대해 배우고 있을 떄 풀이한 것이고, Python 풀이의 경우 작년 겨울방학 때 알고리즘 스터디에서 이 문제를 다루게 되었는데 이전에 C++로 풀이를 했었었기 때문에 Python으로 풀이를 해보았다.

1. C++

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

int LCS_LENGTH(const string& X, const string& Y) {
    int m = X.length();
    int n = Y.length();
    
    vector<vector<int>> c(m+1, vector<int>(n+1, 0));
    
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (X[i-1] == Y[j-1]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else if (c[i-1][j] >= c[i][j-1]) {
                c[i][j] = c[i-1][j];
            } else {
                c[i][j] = c[i][j-1];
            }
        }
    }
    
    return c[m][n];
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string X, Y;
    cin >> X >> Y;

    int result = LCS_LENGTH(X, Y);
    cout << result << endl;
    
    return 0;
}

2. Python

# Question: BJ 9251 (https://www.acmicpc.net/problem/9251)
# Rank : Gold5
# Algorithm : DP, String
import sys
input = sys.stdin.readline

str1 = input().strip() # strip을 통해 문자열을 분리하고 공백을 제거
str2 = input().strip()
DP = [[0]*(len(str2)+1) for _ in range(len(str1)+1)]

for i in range(len(str1)+1):
    for j in range(len(str2)+1):
        if i==0 or j==0:
            DP[i][j]=0
        elif str1[i-1]==str2[j-1]:
            DP[i][j]=DP[i-1][j-1]+1
        else:
            DP[i][j]=max(DP[i-1][j], DP[i][j-1])

print(DP[len(str1)][len(str2)])

결과