[ leetcode 문제풀이 ] Longest Common Subsequence

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

Longest Common Subsequence - LeetCode

(Longest Common Subsequence 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Longest Common Subsequence 문제 설명 >

 

Longest Common Subsequence 문제는 다음과 같다.

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
    ●For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

 

주어진 두 문자열 text1과 text2에 대해 가장 긴 공통 수열의 길이를 리턴하여라. 만약 공통 수열이 없으면 0을 반환하여라.

문자열의 subsequence는 원래 문자열에서 생성된 새로운 문자열로, 나머지 문자의 상대적인 순서를 변경하지 않고 일부 문자를 삭제해 만들어진다. (예를 들어 "ace"는 "abcde"의 subsequence이다.)

common subsequence라는 것은 두 문자열의 공통된 subsequence이다.

 

다음 세 가지 출력 예시가 주어졌다.

주어진 제한 조건은 1 ≤ text1.length, text2.length ≤ 1000, text1과 text2는 소문자로만 이루어져 있다는 것이다.

 

 

 

---

< Longest Common Subsequence 문제 접근 >

 

처음에 어떻게 dynamic programming을 적용해야 할지 감조차도 안왔기에 바로 힌트를 사용하기로 했다.

1. Try dynamic programming, DP[i][j] represents the longest common subsequence of text1[0 ... i] & text2[0 ... j].
2. DP[i][j] = DP[i-1][j-1] + 1, if text1[i] == text2[j] DP[i][j] = max(DP[i-1][j], DP[i][j-1]), otherwise

common subsequence의 길이를 카운트 하는 조건과 카운트 식이 모두 담겨 있기에 그대로 전체 영역을 탐색해주기만 하면 된다. 작성한 코드는 다음과 같다. (Cpp 사용)

int longestCommonSubsequence(string &a, string &b) {
    vector<vector<short>> DP(a.size()+1, vector<short>(b.size()+1));
    for(int i=0; i<a.size();i++)
        for(int j=0; j<b.size();j++)
            if(a[i] == b[j]) 
                DP[i+1][j+1] = DP[i][j] + 1;
            else 
                DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1]);
    return DP[a.size()][b.size()];
}

복잡도 분석을 해보면 n, m을 문자열의 크기라 할 때 시간복잡도 O(nm), 공간복잡도 O(nm)의 값을 갖는다. 

 

위 탐색 과정을 "xabccde"와 "ace" 테스트 케이스에 대한 DP 배열의 값의 그림으로 나타내면 다음과 같다.

 

from leetcode discussion [C++ with picture, O(nm)]

 

Longest Common Subsequence 대한 탐색을 생각해보면 DP 값 할당은 탐색하는 행과 그 바로 전 행에 대한 정보만 사용하여 정보의 업데이트가 일어난다. 즉 필요한 메모리 공간은 2개의 행만 있으면 된다. (가장 긴 common subsequence를 찾으면 되므로 제거한 이전 행에 대한 정보를 다시 사용할 일은 없다.) 따라서, 메모리 공간을 최소한으로 사용하도록 코드를 수정하면 다음과 같다. (Cpp 사용)

int longestCommonSubsequence(string &a, string &b){
    if(a.size()<b.size())			// a와 b 중 더 작은 길이의 문자열로 DP의 열 구성
        return longestCommonSubsequence(b,a);
    
    vector<vector<short>> DP(2, vector<short>(b.size()+1));
    for(int i=0;i<a.size();i++)
        for(int j=0;j<b.size();j++)
            if(a[i]==b[j])
                DP[(i+1)&1][j+1] = DP[i&1][j+1] + 1;
            else
                DP[(i+1)&1][j+1] = max(DP[(i+1)&1][j], DP[i&1][j+1]);
    return DP[a.size()&1][b.size()];
}

수정된 코드에서 복잡도 분석을 해보면 시간복잡도 O(nm), 공간복잡도 O(min(n,m))의 값을 갖는다.

 

DP 값 할당에 대해 불필요한 탐색을 줄여볼 수 있지 않을까?하는 생각도 해보았다. 위 출력 예시 사진에서 c를 찾고 나면 찾은 위치의 오른쪽 아래의 부분 행렬에 대한 탐색만 진행하면 된다. 그렇게 하면 탐색의 횟수 측면에서 유의미한 이득을 볼 수 있을 것으로 생각된다. 그러나 탐색을 시작하는 위치 업데이트, 할당하는 식의 예외 처리, 조건문 등이 추가되어 for문 내부가 복잡해질 것으로 생각되며 실질적인 runtime에는 얼마나 도움이 될지는 미지수이다. (물론 이는 실제로 구현을 해봐야 확인할 수 있는 부분이나, 귀찮아서 이정도 생각에서 마무리한다.)