[알고리즘]최장공통부분수열 구현(LCS)

최장공통부분수열길이 점화식 표현 최장공통부분수열을 일반화해서 점화식을 만들어 보겠습니다. 다시한번 말씀드리면, 현재 우리의목적은 최장공통부분수열의 길이를 구한다는 것입니다. 해가 있다고 가정 LCS(m,n)은 수열 x[1….m]과 y[1….n]의 최장공통부분수열의 해를 구하는 함수입니다. 케이스 정리하기- 현재 비교하는 문자가 같은 경우 LCS(m,n)을 작은 문제를 활용해 풀어봅시다. x[m]과 y[n]이 같은 경우엔 LCS에 해당 문자가 추가되야 합니다. 따라서 현재까지 구한 LCS중 x[m],y[n]을 포함하지 않는 가장 큰 LCS에 현자문자가 더해지므로 1을 더해주면 됩니다. m,n을 각각 i,j로 일반화해서 정리하면 아래와 같습니다 케이스 정리하기- 현재 비교하는 문자가 다른 경우 x[m]과 y[n]이 다른 경우엔, 2가지 경우를 생각해봐야 합니다. 우리가 구하는것은 최장길이 입니다. 따라서 최대한 많은 문자열이 포함 되야 합니다. x[m]과 y[n]은 다르지만 x[m-1]...

원문링크 : [알고리즘]최장공통부분수열 구현(LCS)