[알고리즘] 최장 공통 부분 수열(LCS) - 코딩밥상
최장 공통 부분 수열(Longest Common Subsequence)이란? '공통 부분 수열'은 말 그대로 두개 이상의 수열 사이에 공통으로 존재하는 부분 수열을 말합니다. 따라서 '최장 공통 부분 수열(LCS)'은 여러개의 공통 부분 수열 중 가장 긴 부분 수열을 말합니다. 이 LCS 알고리즘은 두 데이터를 비교할 때 아주 유용합니다. LCS 문제를 동적 계획법으로 풀기 전에 이 문제가 최적 부분 구조로 이루어져 있는지 먼저 확인해야겠네요. X = {x1,x2,x3,...,xi} 와 Y = {y1,y2,y3,...,yj}인 두 문자열이 있다고 하고, 이 두 문자열을 매개 변수로 받아 이들 사이에서 나올 수 있는 LCS의 '길이'를 구하는 함수를 LCS( )라고 하면, 다음과 같은 점화식을 세울 수 있..
