인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

Longest Common Subsequence(LCS)

• <bcdb>는 문자열 <abcbdab>의 subsequence이다.

• <bca>는 문자열 <abcbdab>와 <bdcaba>의 commonsubsequence이다.

• Longest common subsequence(LCS)

  • common subsequence들 중 가장 긴 것

  • <bcba>는 <abcbdab>와 <bdcaba>의 LCS이다

Optimal_Substructure

순환식

int lcs( int m, int n ){
  for ( int i = 0; i <= m; i++ )
    c[i][0] = 0;
  for ( int j = 0; j <= n; j++ )
    c[0][j] = 0;
  for ( int i = 0; i <= m; i++) {
    for ( int j = 0; j <= n; j++ ) {
      if ( x[i] == y[j] )
        c[i][j] = c[i-1][j-1] + 1;
      else
        c[i][j] = Math.max( c[i - 1][j], c[i][ j - 1]);
    }
  }
  return c[m][n];
}

시간복잡도 : θ(mn)