[고급 알고리즘] Dynamic Programming: Longest Common Subsequence

1. Longest Common Subsequence (LCS. 최장 공통 수열)

• 두 수열의 공통 부분 수열 중, 가장 긴 수열을 찾는 문제입니다.

 

부분 수열

• 주어진 수열에서 몇 개의 원소를 선택해 만든 수열
• 원소의 순서는 원래 수열에서의 순서를 유지해야 함

 

점화식

${\displaystyle LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)+1&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}}$

 

예시: XMJYAUZ, MZJAWXU

 

2. 풀이

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

for (int i = 1; i <= a.length; i++) {
    for (int j = 1; j <= b.length; j++) {
        dp[i][j] = a[i] == b[j] ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]);
    }
}

 

 

 

출처

• Wiki - Longest common subsequence