알고리즘 LCS 최장공통부분서열

알고리즘 문제를 푸는데, LCS문제가 종종 나와서 이번에 한번 개념을 확실하게 잡고자 글을 적어봅니다. LCS (Longest Common Subsequence) 두 개의 문자 서열 X,Y가 주어졌을 때, X와 Y에서 공통으로 나타나는 부분 문자 서열을 찾는 알고리즘. 부분 서열의 길이가 최대가 되도록 하는 문자서열을 찾는다. 문제를 푸는 방법? 단순하게 풀기 브루트 포스(Brute-Force Approach) X의 모든 부분 서열에서 Y의 부분 서열인 것의 길이를 구한다음 최댓값을 구한다. X의 부분 서열의 개수는 지수 시간 복잡도를 가진다 따라서 이렇게 푸는 방법은 옳지않다. X = { x1, x2, x3 … x(m-1), x(m) } Y ={ y1, y2, y3 … y(n-1), y(n) } Z =..