[백준(Python/Java)] 9251_LCS

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

9251번: LCS

 

최장 공통 부분수열 문제는 DP를 이용해 풀 수 있는 대표적인 문제입니다.

 

이 문제를 DP를 이용하지 않고 완전탐색으로 풀었을 때에는 모든 각 수열의 모든 가능한 부분수열을 전부 하나씩 구해서 비교해봐야 합니다. 그러면 문자열 s1의 모든 가능한 부분수열을 구할 때 2^(s1의 길이) 만큼의 시간이 소요되고, 이를 s2의 문자열과 비교해봐야 하기 때문에 s2의 길이만큼의 시간이 또 소요됩니다. 따라서 문자열의 길이가 1000만 되어도 절대 제시간안에 문제를 풀 수 없는 구조입니다.

 

따라서, 이 문제는 DP를 이용합니다.

 

dp[i][j]는 s1의 i번째 문자, s2의 j번째 문자까지 활용했을 때의 LCS라고 정의하는데요.

 

그렇다면 dp[i][j]를 결정하는 데는 두 가지 케이스가 생깁니다.

• 만약 s1[i]와 s2[j]가 같다면, 두 문자열의 이전 위치까지의 LCS값에 1을 더한 값이 dp[i][j]가 됩니다.
• 만약 s1[i]와 s2[j]가 다르다면, 두 문자열 중에 해당 위치의 문자열 하나를 제외했을 때 LCS값들 중 더 큰 값이 dp[i][j]가 됩니다.

여기서 두 번째 케이스가 직관적으로 이해가 안 되실 수 있는데요. 한 번 생각을 해보겠습니다.

 

만약 (i, j)위치에서 두 문자열이 다르다면 그 위치에서 LCS값은 절대 그 이전까지 구했던 LCS값보다 증가할 수 없습니다. 새롭게 공통된 부분이 없기 때문이죠. 따라서 그 이전에 구했던 LCS값들 중에서 최대값을 그대로 가져와야하는데, 그 후보는 dp[i-1][j], dp[i][j-1] 두 가지가 되는 것이죠. 왜냐하면 그 이전의 모든 LCS값은 dp[i][j]에 오기 직전인 dp[i-1][j]와 dp[i][j-1]에 반영되어 있기 때문입니다.

 

따라서, 위 코드를 옮기면 아래와 같습니다.

 

* 참고로 문자열 맨 앞에 공백을 추가하는 것과 두 문자열의 길이를 맞춰주는 것은 dp 테이블을 쌓아나갈 때 인덱스에 대한 고려를 쉽게 하기 위함입니다.

 

[풀이 - 파이썬]

import sys
inpurt = sys.stdin.readline

# 두 문자열 입력받기
s1 = " " + input().rstrip()
s2 = " " + input().rstrip()

# 두 문자열의 길이를 동일하게 맞추기
len_s1, len_s2 = len(s1), len(s2)
if len_s1 > len_s2:
    s2 += " " * (len_s1 - len_s2)
else:
    s1 += " " * (len_s2 - len_s1)
length = len(s1)


dp = [[0] * (length) for _ in range(length)]
for i in range(1, length):
    for j in range(1, length):
        # (i, j)의 두 문자열이 일치할 때
        if s1[i] == s2[j]:
            # 해당 위치에서 LCS는 그 지점을 제외한 이전까지 LCS값 + 1
            dp[i][j] = dp[i-1][j-1] + 1
        # (i, j)의 두 문자열이 다를 때
        elif s1[i] != s2[j]:
            # s1의 i번째 문자열을 제외하거나 s2의 j번째 문자열을 제외했을 때 최대 LCS값
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[-1][-1])

 

[풀이 - 자바]

package PS;

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

import static java.lang.Math.max;

public class B_9251 {

    static String s1,s2;
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s1 = " " + br.readLine();
        s2 = " " + br.readLine();

        // 두 문자열의 길이를 동일하게 맞추기
        int len_s1 = s1.length();
        int len_s2 = s2.length();
        int length = max(len_s1, len_s2);
        while(s1.length() < length)
            s1 += " ";
        while(s2.length() < length)
            s2 += " ";

        dp = new int[length][length];
        for(int i = 1; i < length; i++){
            for(int j = 1; j < length; j++){
                // (i, j)의 두 문자열이 일치할 때
                if(s1.charAt(i) == s2.charAt(j)){
                    // 해당 위치에서 LCS는 그 지점을 제외한 이전까지 LCS값 + 1
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                // (i, j)의 두 문자열이 다를 때
                else{
                    // s1의 i번째 문자열을 제외하거나 s2의 j번째 문자열을 제외했을 때 최대 LCS값
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        System.out.println(dp[length-1][length-1]);

    }
}