[알고리즘] LCS(Longest Common Subsequence)

 

참고 자료

• Introduction to Algorihms (CLRS)
• GeeksForGeeks : https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
• SNU OPEN COURSEWARE : https://ocw.snu.ac.kr/sites/default/files/NOTE/Week 6_2.pdf
• Carnegie Mellon Univ : https://www.cs.cmu.edu/~15451-s15/LectureNotes/lecture04.pdf
• Claude AI ( 문법 확인용 )

---

🖐️[알고리즘] LCS(Longest Common Subsequence)

 

LCS는 공통 부분 수열 중에서 길이가 가장 긴 공통 부분 수열, 즉 최장 공통 부분 수열을 의미한다. 최장 공통 부분 수열과 공통 부분 수열, 부분 수열을 쉽게 이해하기 위해서 문자 집합을 생각해보자.

 

문자 집합 “ABC”가 있다고 가정하고 부분 수열을 살펴보자. 부분 수열은 일반적으로 길이가 N인 문자 집합은 2^n개의 부분 수열을 가진다.

 

문자 집합 “ABC”는 길이가 3이므로, 부분 수열은 다음과 같이 총 8개로 나타낼 수 있다.

1. “”
2. “A”
3. “B”
4. “C”
5. “AB”
6. “AC”
7. “BC”
8. “ABC”

 

공통된 부분 수열은 2개의 문자 집합에서 서로에게 공통된 부분들을 의미한다. 다음 아래의 문자 집합 2개를 보자.

 

두 문자 집합에서 각각 길이가 3과 4인 공통된 부분 수열을 1개씩 선정하면 다음과 같다.

 

또, 길이가 5 이상인 공통된 부분 수열은 없기 때문에 위의 <B,C,B,A>가 최장 공통 부분 수열, LCS가 된다. 단, 이때 LCS는 길이가 4인 공통 부분 수열을 의미하므로 추가적으로 존재 할 수 있다.

 

---

☑️ LCS 문제(LCS Problem)

두 Sequence가 존재할 때, 최대 길이의 LCS를 찾는 것이 목표다. LCS 문제는 DP 개념을 통해서 해결할 수 있다.

 

---

☑️ LCS의 특성

---

☑️ LCS의 점화식 표현

 

---

☑️ LCS 문제 구현

LCS 문제는 재귀 함수, 메모이제이션 사용, 상·하향식 DP(테이블)를 통해서 해결할 수 있다.

 

🟧 재귀 함수를 사용한 구현

def lcs(t1, t2,t1_len, t2_len):
    if t1_len == 0 or t2_len == 0:
        return 0
    elif t1[t1_len - 1] == t2[t2_len - 1]:
        return 1 + lcs(t1, t2, t1_len - 1, t2_len - 1)
    else:
        return max(lcs(t1, t2, t1_len - 1, t2_len), lcs(t1,t2,t1_len, t2_len-1))
        

if __name__ == "__main__":
    t1 = "ABCDEFG"
    t2 = "ADDADG"
    
    print(lcs(t1,t2, len(t1), len(t2)))

 

 

🟧 재귀 + 메모이제이션 사용한 구현

# Python implementation of Top-Down DP of LCS problem

# Returns length of LCS for S1[0..m-1], S2[0..n-1]
def lcs(S1, S2, m, n, memo):
    # Base Case
    if m == 0 or n == 0:
        return 0

    # Already exists in the memo table
    if memo[m][n] != -1:
        return memo[m][n]

    # Match
    if S1[m - 1] == S2[n - 1]:
        memo[m][n] = 1 + lcs(S1, S2, m - 1, n - 1, memo)
        return memo[m][n]

    # Do not match
    memo[m][n] = max(lcs(S1, S2, m, n - 1, memo),
                     lcs(S1, S2, m - 1, n, memo))
    return memo[m][n]

if __name__ == "__main__":
    S1 = "AGGTAB"
    S2 = "GXTXAYB"

    m = len(S1)
    n = len(S2)
    memo = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
    print("Length of LCS is", lcs(S1, S2, m, n, memo))

 

🟧 Bottom-Up 접근 구현

def get_lcs_length(S1, S2):
    m = len(S1)
    n = len(S2)

		# DP Table 공간 초기화 -> 0
    dp = [[0] * (n + 1) for x in range(m + 1)]

    # 상향식 접근으로 작은 문제부터 하나하나 풀어나간다.
    # "ABCD"와 "BJED"의 LCS를 찾아가는 과정은 다음과 같다.
    # "A"와 "B"의 LCS 찾기
    # "A"와 "BJ"의 LCS 찾기
    # "A"와 "BJE"의 LCS 찾기
    # ...
    # "ABCD"와 "BJED"의 LCS 찾기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
		        # 문자열이 일치할 경우, 현재 DP Table에 이전 값 + 1을 추가
            if S1[i - 1] == S2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
            # 문자열이 일치하지 않을 경우, 이전 LCS 중 가장 큰 값을 추가
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j - 1])
    return dp[m][n]


if __name__ == "__main__":
    S1 = "AGGTAB"
    S2 = "GXTXAYB"
    print("Length of LCS is", get_lcs_length(S1, S2))