[Algorithm] 백준 LCS 문제 - LCS(9251) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 LCS 문제 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/9251 

9251번: LCS

 

1. 풀이 소스

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.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[str1.length()][str2.length()]);
    }
}

 

 

2. LCS

 

LCS는 Longest Common Subsequence로 두 문자열에서 가장 긴 공통부분 문자열을 찾는 문제를 의미합니다. 부분 문자열은 ABC와 ABC 두 문자열이 동일해야만 하는 것이 아니라, ABDC와 ABC 문자처럼 연속되지는 않지만 하나의 부분 문자열로 ABC를 뽑아낼 수 있는 문자열을 의미합니다.

 

해당 풀이는 다른 소스와 달리 주석을 설정하지 않았는데, 공식처럼 사용되는 부분이 있기 때문입니다. 이 부분을 그림으로 설명하도록 하겠습니다.

 

CAPCAK 문자열과 ACAYKP 두 문자열의 LCS를 구하면 다음과 같이 2차원 배열을 설정할 수 있습니다.

1행에 있는 문자 C와 각 열에 있는 문자 ACAYKP를 하나씩 검사하며, 같은 문자가 있는지 파악합니다.

1행의 C와 2열의 C가 같기 때문에 +1을 진행합니다.

 

1행의 C와 3열의 A는 같지 않습니다. 하지만, 최장 공통 부분 문자열이란, 공통의 긴 부분 문자열 쉽게 말해, 최대 몇 개까지 공통된 문자로 수열을 만들 수 있는가? 를 의미합니다.

따라서, 비록 C와 A는 같지 않지만, 이전 2열에서 C와 C가 동일하기 때문에 1을 그대로 이어서 가져오게 됩니다.

 

 

2행의 A는 2열의 A와 동일합니다. 이 경우는 +1 을 진행해야 하지만, 이전 행과 이전 열의 값에서 +1을 해야 하는 것을 그림에서 파악할 수 있습니다. 왜냐하면, 이전 행과 열을 파악한 결과 같아서 + 1을 했는데, 그 다음행과 그다음열이 또 같기 때문에 이전에 계산한 결과를 그대로 활용해야 하기 때문입니다. 따라서, 하나의 공식을 도출할 수 있습니다.

 

str1.charAt(i) == str2.charAt(j) :

          dp[i][j] = d[i - 1][j - 1] + 1

 

 

 

4행의 C와 6열의 P는 같지 않습니다. 그렇다면 그대로 유지를 해야 합니다. 이때 두 가지를 선택할 수 있습니다.

CAPC / ACAYK, CAPC / ACAYKP의 부분 문자열

먼저 전자는 CA로 2개가 동일하고, 후자는 CAP 3개가 동일합니다.

LCS는 가장 긴 공통 부분 문자열을 구해야 하므로, CAP 동일한 문자열 3개를 선택하게 됩니다.

 

여기서 하나의 공식을 도출할 수 있습니다.

 

str1.charAt(i) != str2.charAt(j) :

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

 

즉, 행과 열 중 1이 더 작은 값을 가지는 값에서 가장 큰 값을 가지는 것을 그대로 유지하는 것입니다.

이러한 원리로 모든 문자를 다 채우게 되면 다음과 같습니다.

 

 

for (int i = 1; i <= str1.length(); i++) {
    for (int j = 1; j <= str2.length(); j++) {
        if (str1.charAt(i - 1) == str2.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[str1.length()][str2.length()]);

 

이를 토대로 dp 마지막에 위치한 값을 각 dp 테이블에서 최대값을 따르게 되는 것을 확인할 수 있습니다.

 

이상으로 LCS 문제 풀이를 마치도록 하겠습니다. 감사합니다.!!!