[DP] LCS(Longest Common Subsequence)

목차

• 1. LCS란? (Substring vs Subsequence)
• 2. 왜 DP여야 하는가? (시간 복잡도의 비밀)
• 3. 점화식의 탄생: 왜 하필 ‘왼쪽’과 ‘위쪽’일까?
• 4. 2차원 배열(DP Table)로의 변환
• 5. 실전 코드: 백준 9251번 적용 (Java)

많은 개발자가 LCS(Longest Common Subsequence) 문제를 처음 접할 때, 그저 “같으면 대각선 + 1, 다르면 위쪽과 왼쪽 중 큰 값”이라는 공식을 암기하곤 합니다. 하지만 왜 그런 공식이 나왔는지 논리적 배경을 이해하지 못하면, 조금만 변형된 문제(LCS 역추적 등)를 만났을 때 속수무책으로 당하게 됩니다. 오늘은 백준 9251번 문제를 통해 LCS의 개념부터 점화식 탄생의 진짜 이유까지 깊이 있게 파헤쳐 보겠습니다.

1. LCS란? (Substring vs Subsequence)

가장 먼저 짚고 넘어가야 할 것은 용어의 정의입니다. 알고리즘 문제에서는 부분 문자열(Substring)과 부분 수열(Subsequence)을 엄격하게 구분합니다.

• 부분 문자열 (Substring): 문자들이 반드시 연속되어야 합니다.
  • 예: ABCDE의 Substring -> ABC, BCD (O) / ACD (X)
• 부분 수열 (Subsequence): 연속되지 않아도 되며, 순서만 지키면 됩니다.
  • 예: ABCDE의 Subsequence -> ACD, ADE (O) / CA (X – 순서 뒤집힘)

우리가 풀고 있는 백준 9251번은 ‘부분 수열(Subsequence)’을 구하는 문제입니다. 즉, 문자열 중간중간을 건너뛰어도 되기 때문에 탐색해야 할 범위가 훨씬 넓고 복잡합니다.

2. 왜 DP여야 하는가? (시간 복잡도의 비밀)

LCS를 구하는 가장 직관적인 방법은 “모든 부분 수열을 다 만들어보고 비교하는 것”입니다. 하지만 이 방식은 치명적인 문제가 있습니다.

• 길이가 N인 문자열의 부분 수열 개수는 약 2^N개입니다.
• 만약 문자열 길이가 1,000자라면, 2¹⁰⁰⁰이라는 천문학적인 연산이 필요합니다. 우주가 멸망할 때까지 계산해도 끝나지 않습니다.

하지만 다이나믹 프로그래밍(DP)을 사용하면 어떨까요? 우리는 두 문자열의 길이만큼의 2차원 표만 채우면 됩니다. 즉, 시간 복잡도가 O(N × M)으로 획기적으로 줄어듭니다. 길이 1,000자라도 1,000,000번(백만 번) 연산이면 충분하죠. 이것이 우리가 LCS에서 DP를 반드시 써야 하는 이유입니다.

3. 점화식의 탄생: 왜 하필 ‘왼쪽’과 ‘위쪽’일까?

이제 핵심인 점화식을 유도해 봅시다. 우리가 구하려는 함수를 F(i, j)라고 정의합니다. 이는 첫 번째 문자열의 i번째, 두 번째 문자열의 j번째까지 고려했을 때의 LCS 길이입니다.

두 문자열의 현재 끝 글자인 S1[i]와 S2[j]를 비교할 때, 상황은 딱 두 가지뿐입니다. 같거나, 다르거나.

상황 1: 두 글자가 같을 때 (Bingo!)

만약 S1[i] == S2[j]라면, 이 글자는 공통 수열에 무조건 포함시키는 것이 이득입니다. 길이 1을 확보했으니, 이제 나머지 앞부분끼리 비교하면 됩니다.

• 논리: “너네 둘 다 합격! 이제 너희는 빠지고 나머지 애들끼리 비교해.”
• 점화식: F(i, j) = F(i-1, j-1) + 1

상황 2: 두 글자가 다를 때 (Conflict!)

문제는 여기입니다. S1[i]는 ‘A’이고, S2[j]는 ‘B’라면 둘이 동시에 매칭될 수는 없습니다. 그렇다면 정답이 될 수 있는 유일한 생존 경로는 다음 두 가지뿐입니다.

1. Case 1: S1의 끝 글자(‘A’)가 쓸모없는 경우
   • ‘A’를 과감히 버리고, S1의 앞부분(i-1)과 S2 전체(j)를 비교하여 기회를 엿봅니다.
   • 함수 호출: F(i-1, j)
2. Case 2: S2의 끝 글자(‘B’)가 쓸모없는 경우
   • ‘B’를 과감히 버리고, S1 전체(i)와 S2의 앞부분(j-1)을 비교하여 기회를 엿봅니다.
   • 함수 호출: F(i, j-1)

이 두 가지 경우 외에 다른 가능성은 없습니다. 우리는 최장 길이를 원하므로, 둘 중 더 큰 값(Max)을 선택해야 합니다.

F(i, j) = Math.max( F(i-1, j), F(i, j-1) )

4. 2차원 배열(DP Table)로의 변환

위의 재귀적 논리를 컴퓨터로 효율적으로 구현하기 위해 메모이제이션(Memoization)을 사용합니다. 변수가 i, j 두 개이므로 바둑판 형태의 2차원 배열이 자연스럽게 탄생합니다.

• F(i-1, j): 행 번호가 하나 줄어듦 -> 바로 위쪽 칸
• F(i, j-1): 열 번호가 하나 줄어듦 -> 바로 왼쪽 칸

결론: ‘왼쪽’과 ‘위쪽’의 정체

결국 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])라는 코드는 배열 모양에 억지로 끼워 맞춘 것이 아닙니다. “매칭되지 않는 끝 글자 중 하나를 제외해 보는 두 가지 논리적 시도”를 2차원 좌표계에 옮겨 놓으니, 기하학적으로 그 위치가 위쪽과 왼쪽이었던 것입니다. 이 기하학적 위치보다 중요한 것은 그 뒤에 숨겨진 ‘논리적 분기’입니다.

5. 실전 코드: 백준 9251번 적용 (Java)

이제 논리는 완벽합니다. 실제 코드로 옮길 때 주의할 점은 인덱스(Index)입니다. 보통 DP 테이블은 (N+1) x (M+1) 크기로 만듭니다.

왜 N+1인가요?
0번 인덱스를 ‘공집합(빈 문자열)’ 상태로 두어야 하기 때문입니다. 만약 N x M으로 만들면, 첫 글자를 비교할 때 i-1이 -1(음수)이 되어 인덱스 에러가 발생합니다. 0행과 0열을 0으로 채워두는 ‘패딩(Padding)’ 기법을 사용하면 조건문 없이 깔끔하게 코드를 짤 수 있습니다.

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 1. 문자열 입력 및 문자 배열 변환
        // toCharArray()를 쓰면 charAt()보다 인덱스 접근이 조금 더 빠릅니다.
        char[] s1 = sc.next().toCharArray();
        char[] s2 = sc.next().toCharArray();
        
        int n = s1.length;
        int m = s2.length;
        
        // 2. DP 테이블 초기화
        // 크기를 n+1, m+1로 잡는 것이 구현의 핵심 팁입니다.
        // 자바에서는 int 배열 생성 시 자동으로 0으로 초기화되므로 별도 작업 불필요.
        int[][] dp = new int[n + 1][m + 1];
        
        // 3. DP 테이블 채우기 (Bottom-Up 방식)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                
                // 주의: dp인덱스는 1부터, 문자열 인덱스는 0부터 시작하므로
                // 문자열을 비교할 때는 i-1, j-1을 사용해야 합니다.
                if (s1[i - 1] == s2[j - 1]) {
                    // Case 1: 글자가 같다면? 
                    // 대각선 위(두 글자 모두 제외된 상태) 값 + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // Case 2: 글자가 다르다면? 
                    // 위쪽(s1문자 제외) vs 왼쪽(s2문자 제외) 중 최댓값 상속
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 4. 정답 출력
        // 표의 가장 오른쪽 아래(모든 문자를 고려한 상태) 값이 최종 정답입니다.
        System.out.println(dp[n][m]);
    }
}

백준 9251번 문제는 단순히 표를 그리는 문제가 아닙니다. "매칭되지 않는 끝 글자를 어떻게 처리할 것인가?"라는 논리적 갈림길에서 시작하여, 중복 계산을 피하기 위해 2차원 평면(DP Table)에 기록해 나가는 최적화의 과정임을 꼭 기억해 주세요. 이 원리를 이해했다면, LCS를 역추적하여 실제 문자열을 출력하는 9252번 문제도 충분히 도전하실 수 있습니다.