💔LCS

 

1. 문제 설명

9251번: LCS

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

www.acmicpc.net

문자열이 두 개 주어졌을 때, 두 문자열의 최장 공통 부분 수열을 구하여라

2. 문제 푸는 원리 설명

부분 수열은 본 수열에서의 숫자의 순서를 지키는 하나의 열이어야 한다. 예를 들어 0이 아닌 양의 정수라는 수열이 있다고 하자. (1, 2, 3, 4, 5, 6, 7, …) 짝수 정수로 이루어진 수열은 해당 정수의 순서를 지키므로 0이 아닌 양의 정수의 부분 수열이다. (2, 4, 6, 8. 10, …) 따라서 최장 공통 부분 수열이라면, 두 문자열에서 공통으로 순서가 같은 문자의 열 중 가장 긴 문자열을 찾으면 된다. 최장 공통 부분 수열을 찾기 위해 DP를 이용해보겠다.

첫 번째 문자열 str1(가로) = “ACAYKP”이고, 두 번째 문자열 str2(세로) = “CAPCAK”일 때, 표의 의미는 다음과 같다. 먼저 파란색 하이라이트가 맞닿은 선의 의미는 문자열 “C”와 문자열 “AC”의 최장 공통 부분 수열이다. 이때는 ‘C’ 하나만 존재하므로 답은 1이다. 두 번째 주황색이 맞닿은 부분은 문자열 “ACAY”와 “CAPC”의 최장 공통 부분 수열의 값이다. 이떄는 ‘C’와 ‘A’가 연속된 공통 부분이므로 “CA”가 공통 부분 수열이고 답은 2이다. 그렇다면 이러한 표는 어떤 점화식으로 구할 수 있을까?

점화식 설명

문자열 “ACA”(가로)와 “CAPCA”(세로)를 들어 설명하겠다. 해당 문자열들의 공통 최장 부분 수열의 길이는 (3,5) 행렬의 값처럼 3이다. “ACA”로 서로 같기 때문이다. 이 둘의 전 문자열을 생각해보자. 각각 “AC”와 “CAPC”였다. 이때, 공통 최장 부분 수열의 값은 “AC” 이다. 둘 다 마지막에 새로운 문자열이 추가 되면서 공통 최장 부분 수열의 길이가 1 증가 하였다. 따라서 만약 공통 문자가 하나 생긴다면 점화식은 dp[x][y] = dp[x-1][y-1] +1 임을 알 수 있다. (dp[x-1]은 dp[x]에서 마지막 문자 하나가 빠진 문자열을 나타냄.) 만약 두 문자열의 끝에 새로운 문자가 추가 되었지만 공통 부분 수열이 늘지 않은 경우 dp의 값은 어떻게 될까? 이때 dp[x][y] = MAX(dp[x-1][y], dp[x][y-1]) 이다. 예를 들어 설명하겠다. 행렬[3,3]을 예로 들면, “CAP”와 “ACA”의 최장 공통부분수열은 “CA”인데 이는 “CA”와 “ACA”의 최장 공통부분수열과도 같다. 따라서 “CAP”와 “ACA”를 비교할 때 새롭게 추가된 문자인 P와 A가 서로 같지 않으면, “CAP”와 “AC”, “CA”와 “ACA”의 최장 공통부분 수열 중 더 큰 값이 계속 답습되는 것이다.

3. 코드 분석

위의 설명을 그대로 코드화 한 것이라 따로 설명은 없다. dp문제는 아이디어 도출이 어렵지 코드 짜는 것은 어렵지 않다는 것을 다시 한번 느낀다.

Copy

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

public class Main{

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

        int N = strArr1.length;
        int M = strArr2.length;

        int [][] dp = new int[N+1][M+1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if(strArr1[i-1] == strArr2[j-1] && dp[i][j-1] < i){
                    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[N][M]);




    }
}