[DP-MultiDimensional][Medium][Good] 1143. Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. text1, text2가 주어질때, 두 text의 가장 긴 공통 subsequence string의 길이를 구하라.

 

 

 

Solution. 

 우선 매우 좋은 문제다.

대놓고 이런 식으로 해결하라라는 과정으로써의 방법이 생략된, DP를 이용해야 쉽게 풀린다는 방법을 알고 있어야 쉽게 풀수 있는 문제.  (Leet code medium 난이도는 이런 문제가 많음. 푸는 방법이나 패턴을 알면 쉬운데, 처음 접하면 감이 안오는 문제가 많다.)

 

 

처음에는 for loop으로 접근해서 backtracking 같은 것들을 시도 해 봤는데, 복잡도만 증가 하였다. 

따라서 문제의 해석과 응용이 매우 중요한 문제라는 것을 알 수 있다. 

 

직전 문제처럼, 두 text를 2차원 블럭과 같이 생각해 봤을 때 

진행 조건과 방향에 대해 생각해 보면 비로소 문제가 풀리기 시작한다.

 

두 블럭의 값이 같으면 얻고자 하는 값에 1 증가 하고 해당 블럭의 위치를 두 축 모두 update 진행 한다.

두 블럭의 값이 다르면, 어느쪽으로든 1 진행 할 수 있다. 

직전 문제와 똑같지 않은가?

 

이번에는 캐시 최적화 까지 적용하였다. 

int longest_dp(vector<int>& vCache, int idx1, int idx2, string& text1, string& text2)
{
    // 어느 축이든 끝에 도달하면 검색은 중지된다.
    if (idx1 >= text1.size() || idx2 >= text2.size())
        return 0;

    int idx = idx2 * text1.size() + idx1;
    if (vCache[idx] >= 0)
        return vCache[idx];

    if (text1[idx1] == text2[idx2])
        vCache[idx] = 1 + longest_dp(vCache, idx1 + 1, idx2 + 1, text1, text2);
    else
        vCache[idx] = max(longest_dp(vCache, idx1+1, idx2, text1, text2), longest_dp(vCache, idx1, idx2+1, text1, text2));

    return vCache[idx];
}
int longestCommonSubsequence(string text1, string text2)
{
    vector<int> vCache;
    vCache.resize(text1.size() * text2.size(), -1);
    return longest_dp(vCache, 0, 0, text1, text2);
}

 

 

적절한 결과를 얻었다.

 

 

Note. TopDown, BottomUp 방법에 따라서 풀이와 실행 시간이 다른것을 알았다. 

두 방법론에 대해 추가적으로 정리 해 볼것.