LCS(Longest Common Sequence) 알고리즘
LCS LCS(Longest Common Sequence)는 주어진 수열들에 대해 가장 긴 공통 부분 수열이다. 예를 들어, 두 문자열 BCDAACD와 ACDBAC에 대한 공통 부분 수열들은 다음과 같다. BC, CDAC, DAC, AAC, AC, CD ... 이러한 공통 부분 수열 중에서 가장 길이가 긴 부분 수열은 CDAC이다. LCS는 $Dynamic Programming$을 이용해 접근할 수 있다. 알고리즘 동작 다음과 같은 두개의 수열 $X$,$Y$가 있다. 우선, $n = length(X), m = length(Y)$ 일 때, $(n+1)*(m+1)$크기의 dp배열이 필요하다. 그리고 다음과 같이 배열을 채운다. dp[i][j]는 $X$의 i번째 원소와 $Y$의 j번째 원소까지 봤을 때, 현재..
