[Boj_9251] LCS

문제 설명

https://www.acmicpc.net/problem/9251

 

▸ 문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

▸ 입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

▸ 출력

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

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 1
• 🔔  문제 유형 : 다이나믹 프로그래밍, 문자열
• 💬  풀이 언어 : Java

 

문제 풀이

문제를 풀기 전, 먼저 최장 공통 부분 수열(LCS, Longest Common Subsequence)에 대해 알아보자.

 

🔍 최장 공통 부분 수열(LCS, Longest Common Subsequence)

LCS는 Longest Common Subsequence의 약자로, 두 수열(문자열)에서 모두의 부분 수열이 되는 수열 중 가장 긴 것을 의미한다.

 

여기서 부분 수열(Subsequence)이란 문자열에서 일부 문자를 선택하여 순서를 유지하면서 만든 수열을 말한다.

즉, 연속적일 필요는 없지만, 문자의 상대적 순서는 반드시 지켜져야 한다.

 

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK이다.

이때 문자는 연속되어 있지 않지만, 두 문자열 모두에서 동일한 순서로 등장한다.

 

LCS 문제는 최적 부분 구조(Optimal Substructure)를 가지므로, 동적 계획법(Dynamic Programming)을 사용해 효율적으로 해결할 수 있다.

 

두 문자열의 각 문자를 하나씩 비교하면서 부분 문제의 해를 기반으로 전체 문제를 해결한다.

 

• 만약 두 문자가 같다면,
  • 두 문자를 포함한 이전 상태의 LCS 길이에 1을 더한다.
  • dp[i][j] = dp[i-1][j-1]+1

• 만약 두 문자가 다르다면,
  • 이전 행(dp[i-1][j]) 또는 이전 열(dp[i][j-1]) 중 더 큰 값을 선택한다.
  • dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

이 과정을 반복하면 dp[a][b]에는 두 문자열의 최장 공통 부분 수열의 길이가 저장된다.

 

코드

메모리 : 15828 KB 
시간 : 96 ms

import java.io.*;

public class Main {
    static char[] str1, str2;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 두 문자열 입력
        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();

        bw.append(lcs(str1.length, str2.length) + "\n");
        bw.flush();
        
        bw.close();
        br.close();
    }

    private static int lcs(int a, int b) {
        dp = new int[a+1][b+1];
        
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                // 현재 비교 중인 두 문자가 같은 경우
                // → 두 문자를 공통 부분 수열에 포함할 수 있으므로
                //   대각선 왼쪽 위(dp[i-1][j-1])의 값에 1을 더함
                if (str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                // 현재 문자가 다를 경우
                // → 공통 수열에 추가할 수 없으므로,
                //   이전 문자까지의 최대 길이 중 큰 값을 가져옴
                //   (즉, 위쪽(dp[i-1][j]) 또는 왼쪽(dp[i][j-1]) 중 더 큰 값 선택)
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        
        return dp[a][b];
    }
}

 

 

 

 

 

📃 reference

• https://st-lab.tistory.com/139
• https://infodon.tistory.com/78