Logest Common Subsequence

리트코드에서 어쩌면 two sum 문제와 함께 가장 유명한 문제에 속하고 DP 문제에 기본이 되는 유형이다.

사실 이 문제는 과거부터 계속 꾸준하게 설명도 듣고 보기도 했지만 DP 유형 문제 특징 상 한번씩 정신줄 놓거나 안하기 시작하면 금방 까먹고 이해하지 못해서 포기했다.

그런데 계속 DP 문제를 풀고 설명도 꾸준하게 듣다보니까 이해가 가서 (80%?) 블로그에 글을 남겨본다.

일단 Longest "Common" Subsequence 라는 제목에서 알 수 있듯이 이 문제는 1차원 DP 로는 해결이 불가능하다. 왜냐면 주어진 두개의 문자열에 해당하는 common sequence를 담아야 하기 때문이다.

그런데 왜 이 문제는 DP가 필요할까? 고민하는게 가장 실력이 빨리 늘 수 있는거같다.

우선 Subproblem 을 생각해야하는데,

1. 같은 캐릭터를 가지고 있다
2. 다른 캐릭터를 가지고 있다.

이때 1번의 경우는 서로 같은 캐릭터를 보고 있다고 하면 더 이상 그 캐릭터는 안보기 때문에 lcs(m-1,n-1) 캐릭터를 봐야한다 (m 은 text1 의 길이 n 은 text2의 길이)

2번의 경우는 다른 캐릭터를 보고 있기 때문에 해당 캐릭터를 제외해야하지만 text1 을 제외해야할수도 있고 text2 를 제외해야하 수도 있다. 그럼으로 lcs(m-1,n) 혹은 lcs(m,n-1).

위에 두 경우를 종합하면 트리가 3갈래로 나뉘게 되고 memoization 이 꼭 필요한 상황이고 이걸 2D 벡터로 해결할 수 있다.

lcs(m-1,n-1) 은 dp[i-1][j-1]
lcs(m,n-1) 은 dp[i][j-1]
lcs(m-1,n) 은 dp[i-1][j]

가로와 세로의 열로 나누어서 비교할 수 있는 방식이 너무 신기했지만 아직은 다시 봐야할 것 같다.

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length(); 
        vector<vector<int>> dp(m+1,vector<int>(n+1,0)); 
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1; 
                } else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
                }
            }
        }

        return dp[m][n]; 
    }
};