[LeetCode 1143] LCS 최장 공통 부분 수열, 재귀로 풀다 TLE 맞고 배운 다이나믹 프로그래밍

"두 문자열에서 공통으로 가장 긴 걸 찾으라고? 그냥 겹치는 부분 찾으면 되는 거 아냐?" 저도 처음 LCS를 만났을 때 딱 이렇게 생각했습니다. 그러다 재귀로 멋지게 짜서 제출했더니 돌아온 건 시뻘건 Time Limit Exceeded였죠. 그것만이 아닙니다. 바텀업 DP로 고쳐 짠 뒤에도 dp[n-1][m-1]로 반환해서 엉뚱한 값을 내고, 글자가 다를 때도 습관처럼 +1을 붙이는 실수를 두 번이나 반복했습니다. LeetCode 토론 게시판을 보면 이 실수들은 놀랍도록 보편적입니다.

최장 공통 부분 수열(Longest Common Subsequence)은 다이나믹 프로그래밍의 교과서 같은 문제입니다. 그만큼 면접에 자주 나오고, 그만큼 사람들이 똑같은 함정에 똑같이 빠집니다. 오늘은 제가 밟았던 지뢰를 순서대로 밟아보면서, 재귀에서 DP로, 그리고 공간 최적화까지 초보자도 따라올 수 있게 정리해보겠습니다.

시작하기 전에: 이 함정부터 피하고 갑시다

본격적으로 풀기 전에 가장 많은 사람이 틀리는 지점부터 짚겠습니다. 바로 부분 수열(subsequence)과 부분 문자열(substring)을 헷갈리는 것입니다. 면접관이 제일 먼저 확인하는 포인트이기도 합니다.

• 부분 문자열은 연속해야 합니다. abcde에서 bcd처럼 딱 붙어 있어야 하죠.
• 부분 수열은 순서만 지키면 중간을 건너뛰어도 됩니다. abcde에서 ace도 부분 수열입니다.

이 둘은 아예 다른 문제입니다. 최장 공통 부분 문자열은 LeetCode 718번, 우리가 풀 최장 공통 부분 수열은 LeetCode 1143번이에요. 면접관 앞에서 이 둘을 섞어 말하면 시작부터 신뢰를 잃습니다. 꼭 구분해두세요.

문제

두 문자열 text1과 text2가 주어졌을 때, 가장 긴 공통 부분 수열의 길이를 반환하세요. 공통 부분 수열이 없으면 0을 반환합니다.

예를 들어 text1 = "abcde", text2 = "ace"라면 공통 부분 수열은 ace이고 길이는 3입니다. text1 = "abc", text2 = "def"처럼 겹치는 글자가 하나도 없으면 0이 되겠죠. 실제로 풀고 검증하려면 LeetCode 1143번에 직접 제출해보는 것을 추천합니다. 온라인 저지가 까다로운 테스트케이스를 대신 만들어주니까요.

1단계: 일단 무식하게 재귀로 풀어봅시다

답이 바로 안 떠오를 때는 가장 단순한 방법부터 시작하는 게 정석입니다. 두 문자열의 첫 글자부터 하나씩 비교해볼게요. 초딩한테 설명하듯 풀어보면 이렇습니다.

• 두 글자가 같으면? 공통 글자를 하나 찾았으니 +1 하고, 둘 다 다음 글자로 넘어갑니다.
• 두 글자가 다르면? 둘 중 하나를 포기해야 합니다. text1의 글자를 건너뛰거나, text2의 글자를 건너뛰거나. 어느 쪽이 더 길지 모르니 둘 다 해보고 큰 값을 고릅니다.

public int longestCommonSubsequence(String text1, String text2) {
    return lcs(text1, text2, 0, 0);
}

private int lcs(String text1, String text2, int i, int j) {
    if (i == text1.length() || j == text2.length()) {
        return 0;
    }
    if (text1.charAt(i) == text2.charAt(j)) {
        return lcs(text1, text2, i + 1, j + 1) + 1;
    }
    return Math.max(lcs(text1, text2, i + 1, j), lcs(text1, text2, i, j + 1));
}

논리는 완벽합니다. 정답도 잘 나오고요. 그런데 저는 여기서 꽤 황당한 실수를 했습니다. 글자가 다를 때도 반사적으로 +1을 붙인 거죠. AlgoCademy나 LeetCode 토론을 보면 이 실수가 얼마나 흔한지 금방 알 수 있습니다. 다들 "논리 상 더 긴 쪽을 골랐으니 +1 아닌가?"라는 함정에 빠집니다.

// 제가 처음 짠 잘못된 코드
return 1 + Math.max(lcs(text1, text2, i + 1, j), lcs(text1, text2, i, j + 1));

"둘 중 더 긴 쪽을 골랐으니 거기에 1을 더하면 되지 않나?" — 그럴듯하게 느껴졌습니다. 그런데 틀렸습니다. 글자가 다를 때는 공통 글자를 찾은 게 아니니 +1이 없어야 합니다. 이렇게 짜면 결과가 항상 과대 계산돼 엉뚱한 값이 나옵니다. 기억하세요 — 글자가 같을 때만 +1입니다.

이 실수를 고쳤더니 이번엔 시간 초과가 왔습니다. 왜일까요?

글자가 다를 때마다 경우의 수가 둘로 쪼개집니다. 이게 문자열 길이만큼 반복되니 재귀 호출이 가지를 치며 폭발하죠. 시간 복잡도가 무려 $O(2^n)$ 입니다. 글자 30개짜리 입력만 들어와도 약 10억 번을 계산하는 셈이라 버틸 수가 없어요.

2단계: 중복 계산을 메모해서 없앱시다 (메모이제이션)

재귀 호출 트리를 그려보면 금방 알아챌 수 있습니다. lcs(2, 3) 같은 똑같은 계산을 여러 갈래에서 반복하고 있다는 것을요. 한 번 구한 답을 어딘가 적어두고 재활용하면 어떨까요? 이게 바로 메모이제이션(top-down DP)입니다.

public int longestCommonSubsequence(String text1, String text2) {
    int[][] memo = new int[text1.length()][text2.length()];
    for (int[] row : memo) {
        Arrays.fill(row, -1);
    }
    return lcs(text1, text2, 0, 0, memo);
}

private int lcs(String text1, String text2, int i, int j, int[][] memo) {
    if (i == text1.length() || j == text2.length()) {
        return 0;
    }
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    if (text1.charAt(i) == text2.charAt(j)) {
        memo[i][j] = lcs(text1, text2, i + 1, j + 1, memo) + 1;
    } else {
        memo[i][j] = Math.max(lcs(text1, text2, i + 1, j, memo), lcs(text1, text2, i, j + 1, memo));
    }
    return memo[i][j];
}

memo[i][j]에 이미 계산한 값이 있으면 그대로 꺼내 씁니다. 같은 부분 문제를 두 번 풀지 않으니 시간 복잡도가 $O(N \times M)$로 뚝 떨어집니다. 여기까지만 해도 LeetCode는 통과합니다.

3단계: 바텀업 DP로 재귀를 걷어냅시다

면접관이 한 발 더 들어와서 "재귀 없이 풀 수 있어요?"라고 물을 수 있습니다. 메모이제이션을 뒤집으면 바텀업 DP가 됩니다. 작은 문제의 답부터 표에 차곡차곡 채워서 큰 문제로 올라가는 방식이죠.

public int longestCommonSubsequence(String text1, String text2) {
    int n = text1.length();
    int m = text2.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

점화식은 딱 두 줄로 요약됩니다.

• 글자가 같으면 왼쪽 위 대각선 값 + 1 ($dp[i-1][j-1] + 1$). 이전까지의 공통 길이에 방금 찾은 글자 하나를 더하는 겁니다.
• 글자가 다르면 위쪽과 왼쪽 중 큰 값 ($\max(dp[i-1][j],\ dp[i][j-1])$). 한 글자를 포기한 두 경우 중 더 나은 쪽을 잇는 거죠.

여기서 초보자들이 가장 많이 깨지는 인덱스 함정이 셋 있습니다. 저 역시 세 번째 함정에서 한 번 틀렸습니다.

• DP 표는 빈 문자열을 위해 행과 열을 하나씩 더 만듭니다($n+1$, $m+1$). 그래서 표의 i번째 행은 문자열의 i-1번째 글자에 대응합니다. 비교할 때 charAt(i - 1), charAt(j - 1)로 1을 빼는 것을 잊으면 엉뚱한 글자를 비교하게 됩니다.
• 최종 답은 반드시 dp[n][m]입니다. dp[n-1][m-1]로 잘못 반환하는 실수가 의외로 흔한데, 저도 처음에 이걸 해서 "왜 1이 작게 나오지?"라고 한참 고민했습니다.
• 시간과 공간 복잡도 모두 $O(N \times M)$입니다. 면접관이 물으면 바로 답할 수 있어야 합니다.

4단계: 공간 복잡도를 $O(N)$으로 줄이기

표를 채울 때 보면 dp[i][j]는 바로 윗줄과 같은 줄 왼쪽만 참고합니다. 그러니까 표 전체를 들고 있을 필요 없이 직전 행과 현재 행, 딱 두 줄만 있으면 됩니다. 이렇게 하면 공간이 $O(N \times M)$에서 $O(N)$으로 줄어듭니다.

public int longestCommonSubsequence(String text1, String text2) {
    int n = text1.length();
    int m = text2.length();
    int[] prev = new int[m + 1];
    int[] curr = new int[m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
        }
        int[] temp = prev;
        prev = curr;
        curr = temp;
    }
    return prev[m];
}

한 행을 다 채우면 prev와 curr를 맞바꿔서 현재 행이 다음 차례의 직전 행이 되도록 합니다. 한 가지 주의할 점이 있어요. 글자가 같을 때 쓰는 대각선 값은 prev[j-1]입니다. 만약 1차원 배열 한 개로 더 줄이려 한다면, 칸을 덮어쓰는 순간 이 대각선 값이 사라지므로 별도 변수로 보관해야 합니다. 면접에서는 보통 두 줄 버전까지만 보여줘도 충분합니다.

면접 팁: 이 문제에서 '진짜' 보여줘야 하는 것

• 부분 수열과 부분 문자열을 정확히 구분해서 말하세요. 첫마디에서 실력이 드러납니다. 면접관들이 꼭 확인하는 포인트입니다.
• 곧장 DP 표를 그리지 말고, 재귀 풀이부터 보여준 뒤 "중복 계산이 보이니 메모이제이션으로 줄이겠습니다"라고 사고 과정을 말로 풀어내세요. 면접관은 답보다 접근 방식을 봅니다.
• 점화식을 쓸 때 "글자가 같으면 대각선, 다르면 위와 왼쪽 중 최댓값"이라고 왜 그런지까지 설명하면 가산점입니다.
• 빈 문자열, 두 문자열이 완전히 다른 경우, 한쪽이 다른 쪽의 부분 수열인 경우 등 엣지 케이스를 먼저 언급하면 꼼꼼한 인상을 줍니다.
• 마지막에 "공간은 두 행만 있으면 되니 $O(N)$으로 줄일 수 있습니다"라고 먼저 제안하면, 최적화를 스스로 찾는 엔지니어로 보입니다.

---

정리

LCS는 재귀에서 출발해 DP로 진화하는 과정을 그대로 보여주기 좋은 문제입니다. 오늘 밟아본 길을 한 줄로 요약하면 이렇습니다.

• 무식한 재귀: 논리는 맞지만 $O(2^n)$으로 터집니다. 글자 다를 때 +1 붙이는 실수 주의.
• 메모이제이션: 중복 제거로 $O(N \times M)$ 달성.
• 바텀업 DP: 재귀를 걷어내고 표로 정리. charAt(i-1) 인덱스 오프셋과 dp[n][m] 반환 위치 꼭 확인.
• 공간 최적화: 두 행만 남겨 $O(N)$.

면접에서 이 문제를 만나면 코드부터 두드리지 말고, "재귀로 짜면 이렇고, 여기 중복이 보이니 DP로 바꾸겠습니다"라고 생각의 흐름을 먼저 말해보세요. diff 명령어나 생물정보학의 DNA 서열 정렬도 바로 이 LCS에서 출발합니다. 알고리즘 하나가 현실의 도구로 이어지는 걸 알고 있다는 점까지 곁들이면, 면접관에게 오래 남는 답변이 됩니다.