LCS(9251)

Longest Common Subsequence를 구하는 문제

문제

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

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

입력

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

출력

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

예제 입력

ACAYKP
CAPCAK

예제 출력

4

https://www.youtube.com/watch?v=P-mMvhfJhu8

이 강의를 통해서 어떻게 알고리즘이 진행되는지 쉽게 알 수 있었다

9251

사이즈가 각 배열의 크기보다 1이 큰 2차원 배열을 만들고

1. 0번째 가로, 0번째 세로를 0으로 채운다

2. 하나씩 채워갈껀데, dp의 i, j 번째를 정하기 위해서는 arr1[i-1] 와 arr2[j-1]을 확인해야한다. 왜냐하면 채워가는 부분은 1,1부터 시작해서 진행하고, 그림을 보면알겠지만 dp배열의 0,0은 공집합을 위한 0이기 때문

3. • 만약 arr1[i-1]과 arr2[j-1]이 같다면 ->dp의 i-1, j-1의 숫자에 1을 추가한 숫자를 dp의 i, j에 넣어줌

   • 만약 같지 않다면 -> dp의 i, j-1과 dp의 i-1, j 을 비교해서 큰 숫자를 dp의 i, j에 넣어줌

4. 이렇게 모든 표를 채워주고 가장 큰수(결국은 맨 마지막에 있는 배열이 가장 큰 수가 됨)가 LCS의 숫자가 된다

5. 여기까지가 문제에서 원하는 해답을 찾는 과정이고 위 링크 영상에서는 그 수열이 무엇인지까지 찾는 과정을 알려주기 떄문에 필요할 때 가서 찾아보면 될듯 하다

풀이

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

public class Main{
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //toCharArray()함수를 이용하면 char 형태의 배열로 만들어줄수 있다
        char arr1[] = br.readLine().toCharArray();
        char arr2[] = br.readLine().toCharArray();
        int dp[][] = new int[arr1.length+1][arr2.length+1];

        for(int i=1; i<=arr1.length; i++){
            for(int j=1; j<=arr2.length; j++){
                if(arr1[i-1] == arr2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        System.out.println(dp[arr1.length][arr2.length]);
    }

}

백준