[Java][백준][골드 5] LCS - 9251

1. 문제 정보

• 문제 번호: 9251번
• 문제 제목: LCS
• 알고리즘 분류: 동적 계획법 (Dynamic Programming)
• 난이도: Gold 5

 

2. 문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 되며 길이는 4입니다.

입력

• 첫째 줄과 둘째 줄에 두 문자열이 주어진다. (최대 1000글자)

출력

• 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

3. 풀이 전략

핵심 아이디어: 동적 계획법 (DP)

이 문제는 전형적인 2차원 DP 문제입니다. 두 문자열의 길이를 각각 $L1, L2$라고 할 때, dp[L1+1][L2+1] 배열을 선언하여 부분 문제를 해결합니다.

점화식 설계

두 문자열을 $S1, S2$라 하고, 인덱스를 $i, j$라고 할 때:

1. 문자가 같은 경우 ($S1[i] == S2[j]$):
   • 두 문자가 공통 부분 수열에 포함되므로, 이전까지의 최장 길이에 1을 더합니다.
   • dp[i+1][j+1] = dp[i][j] + 1
2. 문자가 다른 경우 ($S1[i] \neq S2[j]$):
   • 두 문자 중 하나를 제외했을 때의 최댓값을 가져옵니다.
   • dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j])

시간 복잡도

• 두 문자열의 길이를 $N, M$이라 할 때, 2중 for문을 수행하므로 **$O(N \times M)$**의 시간 복잡도를 가집니다. $1000 \times 1000 = 1,000,000$이므로 제한 시간 내에 충분히 해결 가능합니다.

 

4. 정답 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 두 문자열 입력 받기
        String s1 = br.readLine();
        String s2 = br.readLine();

        int l1 = s1.length();
        int l2 = s2.length();

        // DP 테이블 초기화 (인덱스 편의를 위해 길이에 +1)
        int[][] dp = new int[l1 + 1][l2 + 1];

        // 2중 루프를 통한 DP 테이블 채우기
        for (int i = 0; i < l1; i++) {
            for (int j = 0; j < l2; j++) {
                // 문자가 같으면 대각선 위 값 + 1
                if(s1.charAt(i) == s2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                } 
                // 문자가 다르면 위쪽 혹은 왼쪽 값 중 큰 값 선택
                else {
                    dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
                }
            }
        }

        // 최종 결과 출력 (두 문자열 전체의 LCS 길이)
        System.out.println(dp[l1][l2]);
    }
}

 

5. 정리 및 복기

• 문자열 인덱스와 DP 인덱스: 문자열의 $i, j$번째 문자를 비교할 때 dp 배열에는 i+1, j+1 위치에 값을 저장하여 인덱스 범위를 벗어나는 처리를 깔끔하게 해결했습니다.
• LCS의 응용: 이 알고리즘은 파일 비교(diff), 생물정보학(DNA 서열 분석) 등 다양한 분야에서 활용되는 중요한 기초 알고리즘입니다.
• 추가 학습: 만약 LCS의 '길이'가 아니라 '실제 수열'을 출력해야 한다면, 완성된 DP 테이블을 역추적(Backtracking)하는 과정을 추가하면 됩니다.