📖 [백준알고리즘 풀이] Q.9251 LCS 문제 풀이 - java

📖 문제

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

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

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

입력

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

출력

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

🔍 접근법

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제입니다.

수열 문제의 유형 중 하나 입니다.

각 문자열의 부분집합들을 비교해 가장 긴 공통 부분 수열을 찾는 문제입니다.

동적프로그래밍으로 풀이가 가능합니다.

table

각 부분집합들에 대해 위와 같이 표를 그려보면 점화식을 찾을 수 있습니다.

word1 문자열의 i번째 문자와 word2 문자열의 j번째 문자가 같은 문자일 때 => word1.charAt(i)==word2.charAt(j)

word1의 i-1번째까지의 문자열과 word2의 j-1번째까지의 두 문자열 간의 LCS 길이가 1이 증가합니다.

// word1.charAt(i-1)==word2.charAt(j-1) 문자열의 인덱스가 0부터 시작하기 때문!

if(word1.charAt(i-1)==word2.charAt(j-1)){
    dp[i][j] = dp[i-1][j-1]+1;
}

왜냐하면 word1의 i-1번째까지의 문자열과 word2의 j-1번째까지의 두 문자열 간의 공통 부분 수열의 길이가 x 일때

word1의 i번째 문자와 word2의 j번째 문자가 동일하면 그 전까지의 공통 부분 수열에 공통 문자 하나가 더 추가되는 것이기 때문입니다.

공통 부분 수열의 길이 1 증가 => dp[i][j] = dp[i-1][j-1]+1

나머지 경우인 word1 문자열의 i번째 문자와 word2 문자열의 j번째 문자가 다른 문자일 때는

테이블의 바로 전 열의 공통 부분 수열 길이와 dp[i][j-1] 테이블의 바로 전 행의 공통 부분 수열 길이 dp[i-1][j] 를 비교해 더 긴 길이를 넣어주면 됩니다.

dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

💻 코드

package problem.dynamic;

import java.io.*;

public class Main_9251 {
    static int dp[][];
    static StringBuilder sb;
    static String word1;
    static String word2;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        sb = new StringBuilder();
        solve();
        bw.flush();
        bw.close();
    }
    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        word1 = br.readLine();
        word2 = br.readLine();
        dp = new int[word1.length()+1][word2.length()+1];
        br.close();
    }
    public static void solve() {
        for(int i = 0; i <= word1.length(); i++)
            dp[i][0] = 0;
        for(int i = 0; i <= word2.length(); i++)
            dp[0][i] = 0;

        for(int i=1; i<=word1.length(); i++){
            for(int j=1; j<=word2.length(); j++){

                // word1.charAt(i-1)==word2.charAt(j-1) 문자열의 인덱스가 0부터 시작하기 때문!
                if(word1.charAt(i-1)==word2.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]);
                }
            }
        }
        System.out.println(dp[word1.length()][word2.length()]);
    }
}

Written on February 16, 2021