문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

문제 풀이

알고리즘 문제를 풀다 보면,아무리 고민해봐도 도저히 해결법이 생각나지 않는 문제도 있고, 그러한 문제의 해결법을 찾아보았을 때 ‘이딴걸 어케 알아!’ 싶은 순간이 있다. 알고리즘 문제 풀이를 처음 시작했던 때, 문제들마다 유형이 있다는 사실조차 제대로 몰랐을 시절에는 자주 느꼈던 감정이었고, 최근 유형을 알고 실력이 조금씩 늘면서 거의 느끼지 못했던 감정이었는데 오랜만에 이 문제를 풀며 느낄 수 있었다.
아무리 고민해보고 이리저리 해결법을 모색해봐도 명쾌하게 떠오르는 해답이 없었는데 결국 해답을 찾아보니 LCS 알고리즘이라는 이름으로 따로 이름까지 있는 문제였다. 해결법 자체는 굉장히 간단했는데 코딩테스트 시험을 볼 때 관련지식이 전무한 상태에서 이 문제의 점화식을 도출해낼 수 있을까? 하면 잘 모르겠다. 그렇기에 여러 문제를 많이 풀어봐야하는 것이겠구나 싶을 뿐이다. 결국 풀이가 아니라 변명처럼 되어버렸는데 일단 풀이는 다음과 같다.
dp배열을 2차원 배열로 잡는다. dp[i][j]는 두 문자열의 알파벳 i, j 까지의 최장 공통 부분수열의 길이가 된다. 우리는 이중 반복문으로 두 문자열의 각 알파벳을 비교하며 두 알파벳이 다르다면 dp[i][j]=max(dp[i-1][j],dp[i][j-1])로 이전까지의 비교에서 최장 공통 부분수열의 길이의 최대값을 가져오며 유지한다. 두 알파벳이 같다면 현재 비교하는 두 알파벳이 빠진 dp[i-1][j-1]에서 1을 더하여 최대값을 갱신한다.

코드

 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    string a, b;
    cin >> a >> b;
    a=" "+a;
    b=" "+b;
    vector<vector<int>> dp(1005,vector<int>(1005,0));
    dp[0][0]=0;//계산의 편의를 위해 각 문자열의 처음을 비워준다
    for(int i=1; i<a.length(); i++) {
        for(int j=1; j<b.length(); j++) {
            if(a[i]!=b[j]) dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            else dp[i][j]=dp[i-1][j-1]+1;
        }
    }//위의 풀이대로 계산하며 dp배열을 채워준다
    cout << dp[a.length()-1][b.length()-1];
}