알고리즘 : LCS (최장 공통 부분수열)

LCS (Longest Common Subsequence)

문자열 x, y가 있을 때 x와 y에서 공통으로 나타나는 부분 문자 수열 중 최대 길이를 갖는 문자 수열

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

 

재귀적으로 정의

c(i, j) : 수열 xi와 yj의 LCS의 길이

 

기저조건 (종료조건)

• i =0 또는 j = 0이면 c(i, j) = 0이 된다

재귀조건

• xi = yj이면 c(i, j) = c(i-1, j-1) + 1
• xi != yj이면 c(i,j) = max(c(i, j-1), c(i-1, j))

int lcs (String x, String y){
	int m = x.length();
    int n = y.length();
    
    if(m == 0 || n == 0){
    	return 0;
    }else{
    	if(x.charAt(m-1) == y.charAt(n-1))
        	return lcs(x.substring(0, m-1), y.substring(0, n-1)) + 1;
    	else
        	return Math.max(lcs(x, y.substring(0, n-1)), lcs(x.substring(0, m-1), y));
    }
}

 

하지만 재귀를 사용하면 중복되는 부분 문제가 생긴다

c(i, j) = 0

c(i, j) = c(i-1, j-1) + 1

c(i, j) = max(c(i, j-1), c(i-1, j))

 

=> 메모이제이션(memoization) : 이미 계산한 값을 테이블에 저장

=> 하향식에서 상향식으로 전환하기

 

 

백준에 LCS 대표 문제가 있어서 이 문제를 통해 LCS DP 코드를 보여주겠다.

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

package boj;

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

public class Main_gold5_9251_LCS {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String a = br.readLine();
		String b = br.readLine();
		int lcs[][] = new int[a.length() + 1][b.length() + 1];
		for (int i = 0; i < a.length(); i++) {
			for (int j = 0; j < b.length(); j++) {
				if (a.charAt(i) == b.charAt(j)) {
					lcs[i + 1][j + 1] = lcs[i][j] + 1;
				} else {
					lcs[i + 1][j + 1] = Math.max(lcs[i][j + 1], lcs[i + 1][j]);
				}
			}
		}
		
		System.out.println(lcs[a.length()][b.length()]);
	}
}

이렇게 하면 최종 LCS의 길이는 알 수 있다.

만약 LCS가 어떻게 구성되었는지 알고 싶다면 어떻게 해야할까?

 

최적해의 재구성

대각선에서 오면 1, 위에서 오면 2, 왼쪽에서 오면 3

int[][] b = new [a.length()+1][b.length()+1];

for (int i = 0; i < a.length(); i++) {
    for (int j = 0; j < b.length(); j++) {
        if (a.charAt(i) == b.charAt(j)) {
            lcs[i + 1][j + 1] = lcs[i][j] + 1;
            b[i+1][j+1] = 1;
        } else {
        	if(lcs[i + 1][j] > lcs[i][j + 1]){
            	lcs[i + 1][j + 1] = lcs[i + 1][j];
                b[i+1][j+1] = 2;
            } else{
            	lcs[i + 1][j + 1] = lcs[i][j + 1];
                b[i+1][j+1] = 3;
            }
        }
    }
}

배열 b에 기록을 해주고 맨 끝에서부터 하향식으로 찾아나가면 되는 것이다.

void get_lcs(int i, int j){
	if(i==0 || j==0) {
    	return "";
    } else {
    	if (b[i][j] == 1){
        	return get_lcs(i-1, j-1) + x.charAt(i);
        } else if (b[i][j] == 2) {
        	return get_lcs(i-1, j);
        } else {
        	return get_lcs(i, j-1);
        }
    }
}

lcs를 얻는 과정이다.

 

1이 된 부분이 같은 부분이니까 1이 된 부분만 출력해주면 된다.