[알고리즘] LCS (Longgest Common Subsequence), 최장 공통부분 수열 찾기

LCS, 최장 공통부분 수열 찾기 알고리즘은 두 문자열의 부분 수열 중에서 가장 긴 부분 수열을 구할 때 적용할 수 있는 알고리즘입니다. Dynamic programming (동적 계획법) 방식으로 알고리즘을 구현할 수 있고, 그렇기 때문에 top-down memoization, bottom-up 방식 두 가지로 구현 방식이 나뉘게 됩니다. Dynamic programming 방식으로 알고리즘을 구현하기 위해서는 전체 문제가 Optimal substructure 구조를 가져야 합니다. 이 optimal substructure는 현재 문제의 optimal solution이 이 문제의 sub problem의 optimal solution을 포함하는 것을 의미합니다. 조금 더 쉬운 이해를 위해서 수업 시간에 배웠던 수식적인 내용으로 정리를 해보겠습니다. 두 개의 문자열을 X, Y라고 지칭하고, X_m = <x_1, x_2, ... , x_m>, Y_n = <y_1, y_2, ... , y...

원문링크 : [알고리즘] LCS (Longgest Common Subsequence), 최장 공통부분 수열 찾기