LCS(Longest Common Subsequence) + Java

최장 공통부분 수열은(LCS, Longest Common Subsequence) 여러 개의 수열이 주어졌을 때 두 수열의 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 방법이다.

 

구하는 방법은 하나의 수열을 순서대로 다른 수열의 모든 문자와 비교하여 같은지 비교하는데, 동적 계획법(DP)을 활용하여 문제를 푼다.

 

1. 만약 같다면 현재 비교하고 있는 [n][n] 번 위치의 문자 이전에 매치됐던 [n-1][n-1] 번 위치에 있는 문자에 더한다.

2. 만약 다르다면 비교하기 이전에 나왔던 가장 긴 길이를 갖도록 하기 위해서 [n][n-1] 위치의 값과 [n-1][n] 위치의 값을 비교하여 큰 값을 가진다.

3. 배열의 최종 위치의 숫자는 가장 긴 수열의 길이를 갖게 된다. 

 

예시: ABCD, BZDCD => BCD

 

예시에서 ABCD에서 B가 BZDCD에서 B와 매치됐을 때([2][1] 번 위치) A는 매치된 내용이 없기 때문에 1이 되고 ABCD의 C가 매치될 때는 B([2][1] 번 위치)에서 매치된 내용이 있기 때문에 2가 된다.

 

예시에서 ABCD의 B가 BZDCD의 Z와 비교할 때 매치하지 않기 때문에 [1][2] 번 위치와 [2][1] 번 위치의 값을 비교하여 큰 값인 1이 된다.

 

아래는 비교가 끝난 배열이다.

	0	B	Z	D	C	D
0	0	0	0	0	0	0
A	0	0	0	0	0	0
B	0	1	1	1	1	1
C	0	1	1	1	2	2
D	0	1	1	2	2	3

 

문제 : 백준 알고리즘 9251번 문제

문제 풀이 코드

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

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

        int aLen = a.length;
        int bLen = b.length;
        int[][] lcs = new int[aLen + 1][bLen + 1];

        for(int i = 1; i <= aLen; i++) {
            for(int j = 1; j <= bLen; j++) {
                if(a[i-1] == b[j-1]) {
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                } else {
                    lcs[i][j] = lcs[i-1][j] > lcs[i][j-1] ? lcs[i-1][j] : lcs[i][j-1];
                }
            }
        }

        System.out.println(lcs[aLen][bLen]);
    }
}