LeetCode 1143 - Longest Common Subsequence

두 문자열 text1과 text2가 주어졌을 때, 상대적인 순서를 유지하면서 양쪽에 공통으로 나타나는 가장 긴 부분 수열(Subsequence)의 길이를 구하는 Medium 문제다. 2차원 DP 테이블을 구성하여 두 문자열의 접두사 단위로 부분 문제를 정의하고 상향식(Bottom-Up)으로 풀이했다.

문제 링크 & 설명

문제 링크: 1143. Longest Common Subsequence
요약: 두 문자열 text1, text2 사이의 최장 공통 부분 수열(LCS)의 길이를 반환한다. 공통 부분 수열이 없다면 0을 반환한다.

부분 문자열(Substring)과 달리 부분 수열(Subsequence)은 연속되지 않아도 되지만 순서는 바뀌지 않아야 한다. 예를 들어 "abcde"와 "ace"의 LCS는 "ace"이므로 길이는 3이다.

접근 방법

dp[i][j]를 text1[0...i-1]과 text2[0...j-1]의 LCS 길이로 정의한다. 빈 문자열과의 비교를 위해 테이블 크기는 (m + 1) x (n + 1)로 설정하고 0으로 초기화한다.

m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
    for j in range(1, n + 1):
        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])

문자가 일치하는 경우 (text1[i-1] == text2[j-1]): 해당 문자를 공통 수열에 포함할 수 있으므로, 두 문자 모두를 제외했던 이전 상태의 값에 1을 더한다 (dp[i-1][j-1] + 1).
문자가 일치하지 않는 경우 (text1[i-1] != text2[j-1]): 둘 중 하나를 제외한 두 가지 경우 중 더 큰 LCS 길이를 취한다 (max(dp[i-1][j], dp[i][j-1])).

최종적으로 dp[m][n]에 두 문자열 전체에 대한 LCS 길이가 저장된다.

복잡도 분석

시간 복잡도: O(m × n)
- 두 문자열의 길이를 각각 m, n이라 할 때 크기가 (m + 1) × (n + 1)인 DP 테이블의 각 셀을 상수 시간에 채운다.
공간 복잡도: O(m × n)
- (m + 1) × (n + 1) 크기의 2차원 배열을 할당하여 사용한다.

구현 코드

class Solution:

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                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]

요약 및 회고

문자열 간의 최장 공통 부분 수열 문제는 현재 비교하는 두 문자가 일치하는지 여부에 따라 상태 전이식이 명확하게 갈린다. 일치할 때는 대각선 이전 단계(dp[i-1][j-1])에서 1을 더하고, 불일치할 때는 위쪽과 왼쪽의 최댓값을 취하는 점화식 구조를 시각적으로 이해해두면 유사한 2D DP 문제에서도 상태를 직관적으로 설계할 수 있다.