[백준 JAVA] 9251번: LCS

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

 

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

 

두 문자열에서 순서를 유지하면서 일부 문자를 골라 만든 "공통 부분 수열(Subsequence)" 중 가장 긴 길이를 구하는 문제입니다.

 

평소 문자열 문제는 코테에서 별로 나오지 않는다고 생각해 공부를 좀 등한시 했었다. 

 

이번 기회에 차근차근 풀어보자

 

정답을 보기전에 혼자 풀어보자면

 

1. 문자열 길이가 1000이므로 가장 멍청하게 푼다면 1000개를 원소로가진 집합의 부분수열은 2의 1000승이고 이걸다시 다른 문자열의 부분집합과 비교해야하므로 2의 2000승이 걸린다. 1초에 O(2^30) 정도가 걸리므로 이 방법은 안된다.

 

2. 부분수열을 먼저 구해놓으면 시간초과가 생기므로 i를 증가시키며 부분수열을 만들면서 공통되는 부분을 찾아야 된다.

 

3. 찾을때마다 정답을 초기화 해줄꺼냐 다찾고 끝까지 갔을때 정답을 찾을꺼냐 이중포문을 돌리면될꺼같기도하다.

 

4. 근데 이러면 건너뛰는게 이득인 경우에도 무조건 찾게되므로 이부분은 틀린거 같아서 답을 찾아보았다.

 

찾아보니 DP 메모이제이션을 활용해 누적합과 같은 형식으로 최대길이를 구해야한다. 뭔가 접근방법은 비슷했지만 생각하지 못했을꺼같았다.

 

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

public class Main {
    public static char[] str1, str2;
    public static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();

        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[i - 1] == str2[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]);
    }
}

 

 

 

이 문제를 접했을때 헷갈리기 쉬운 부분은

 

Subsequence(부분 수열) 은 연속적일 필요가 없음.
→ 단, 원래 순서는 지켜야 함.

Substring(부분 문자열) 과 다르다. Substring은 반드시 연속되어야 함.

 

이 문제는 부분 문자열이기 때문에 이 방법으로 풀 수 있는것이다.

 

dp[i][j] = 문자열 A의 처음 i글자와 문자열 B의 처음 j글자까지 고려했을 때 LCS의 길이를 뜻한다..

 

점화식은 다음과 같다

만약 A[i-1] == B[j-1] (즉, 마지막 글자가 같다면):

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

 

그렇지 않다면:

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

 

예시를 보자면 다음과 같다.

i\j	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

마지막 값 dp[6][6] = 4 → 정답이 나오게 된다.

 

 DP 문제를 최근에 많이 안풀어서 처음에 이해할때 더 어렵게 느껴졌던것같다.

 

DP문제도 많이 풀어보자.