[백준] BOJ_9251 LCS

1. 문제 정보

• 문제 요약: 두 문자열이 주어졌을 때, 모두의 부분 수열이 되는 문자열 중 가장 긴 것의 길이를 계산합니다. (부분 수열은 연속할 필요가 없음에 유의합니다.)
• 주요 제약: 각 문자열의 길이는 최대 1,000자입니다.
• 난이도: Gold V
• 문제 링크: BOJ 9251 - LCS

---

2. 접근 방식

1) 문제의 본질

이 문제의 핵심은 '부분 수열(Subsequence)'의 정의에 있습니다. '부분 문자열(Substring)'과 달리 문자들이 반드시 인접해 있을 필요가 없습니다.

만약 우리가 두 문자열의 모든 부분 수열을 생성하여 비교하는 브루트 포스(Brute-force) 방식을 택한다면, 길이가 인 문자열의 부분 수열 개수는 개이므로 시간 복잡도는 $O(2^N)$이라는 처참한 수치를 기록하게 됩니다. 인 이 문제에서는 절대 불가능한 방식이죠. 따라서 우리는 최적 부분 구조(Optimal Substructure)를 찾아 하위 문제의 해를 재활용하는 DP로 선형 환원을 시도해야 합니다.

2) 알고리즘 설계

두 문자열 와 를 비교할 때, 각 문자열의 끝에서부터 비교하며 경우의 수를 나눕니다.

1. 두 문자가 같은 경우: 해당 문자는 LCS의 일원이 될 확정적인 후보입니다. 따라서 두 문자를 제외한 나머지 문자열들로 만든 LCS 길이에 +1을 해줍니다.
2. 두 문자가 다른 경우: 두 문자 중 하나를 제외했을 때의 최댓값을 취합니다. 즉, 의 현재 문자를 제외한 경우와 의 현재 문자를 제외한 경우 중 더 큰 값을 계승합니다.

이를 위해 2차원 배열 $DP[i][j]$를 선언하며, 이는 '문자열 A의 번째 문자까지와 문자열 B의 번째 문자까지 고려했을 때의 LCS 길이'를 의미하게 됩니다.

3) 점화식 및 수식

문자열 의 번째 문자를 , 문자열 의 번째 문자를 $B[j]$라고 할 때 점화식은 다음과 같습니다.

---

3. 코드 구현

입력받은 로직을 바탕으로 가독성을 정리한 Java 11 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        // 문자열을 char 배열로 변환하여 접근성 향상
        char[] A = br.readLine().toCharArray();
        char[] B = br.readLine().toCharArray();
        
        // 인덱스 에러 방지 및 초기값(0) 처리를 위해 크기를 +1 설정
        int[][] dp = new int[A.length + 1][B.length + 1];

        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                // 문자가 같은 경우: 대각선 위(이전 단계) 값 + 1
                if (A[i - 1] == B[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]);
                }
            }
        }

        // 최종 결과 출력
        System.out.println(dp[A.length][B.length]);
    }
}

---

4. 회고 및 배운 점

시간 복잡도 분석

• 시행착오 가능성: 만약 이 문제를 단순 재귀(Backtracking)로 풀었다면 $O(2^N)$의 복잡도로 인해 환경에서 Time Limit Exceeded를 마주했을 것입니다.
• DP의 효율성: 위 풀이는 두 문자열의 길이를 각각 $N, M$이라 할 때, 2중 루프를 통해 배열을 채우므로 $O(N \times M)$의 시간 복잡도를 가집니다. $1,000 \times 1,000 = 1,000,000$ 연산으로, 1초 제한 시간 내에 매우 여유롭게 통과할 수 있습니다.

구현 디테일

• Padding (Zero-indexing): $dp$ 배열의 크기를 length + 1로 설정하는 것은 매우 전형적이지만 강력한 테크닉입니다. 이는 혹은 참조 시 발생할 수 있는 IndexOutOfBounds 예외를 방지하며, 빈 문자열과의 비교 결과(0)를 자연스럽게 기저 사례(Base Case)로 포함시킵니다.
• 공간 최적화: 현재는 공간을 사용하지만, 사실 $DP[i][j]$를 구할 때 직전 행($i-1$)정보만 필요하므로 토글링(Toggling) 기법이나 1차원 배열을 이용해 수준으로 공간 복잡도를 최적화할 수도 있습니다. (물론 이 문제의 메모리 제한 256MB 내에서는 현재 풀이로도 충분합니다.)