LCS(Longest Common Subsequence)는 문자열 A,B가 있을 시, 가장 길이가 긴 공통 부분 문자열을 찾는 알고리즘입니다. 여기서 부분 문자열이라는 것은 연속된 문자열이 아닌 부분 문자열을 뜻합니다. 예로들어, 'HAYOUNG'과 'AONG'이라는 문자열이 있을 시, 공통된 부분문자열은, {A}, {A,O}, {A,N}, {A,G}, .. ,{A,O.N,G} 가 있죠. 그리고 여기서 가장 긴 부분 문자열은 'AONG'입니다. LCS를 푸는 알고리즘은 Dynamic Programming을 이용하며 O(mn), (m = len(A), n = len(B)) 의 시간복잡도를 가지고 해결할 수 있습니다. 푸는 절차는 다음과 같습니다. 먼저, Dynamic Programming을 적용하기 위해 ..