[DP#1] 최장공통부분수열(LCS)

최장공통부분수열(Longest Common Subsequence)

최장공통부분수열이란 두 수열이 주어졌을 때, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 말하며, 주로 문자열 비교에서 많이 사용되는 기법이다.
예를 들어, ABCD와 ACDF라는 두 개의 문자열의 최장공통부분수열은 ACD이다.

최장공통부분수열을 찾는 가장 일반적인 방법은 동적계획법(Dynamic Programming)을 사용하는 것이다.
동적계획법을 활용하여 길이가 m과 n인 두 문자열의 최장공통부분수열을 구하는 경우 시간복잡도는 O(mn)으로 가장 효율적이다.

최장공통부분수열을 구하는 과정

1. 두 문자열을 X와 Y이며 X의 길이를 m, Y의 길이를 n이라고 가정
2. 각 문자열의 부분수열 정보를 담는 이차원 배열(DP[m][n])을 생성
3. 이차원 배열을 돌며 아래 연산 반복
   1) 두 문자가 같은 경우, 이전 대각선 위치의 값에 1을 더하여 현재 위치의 값을 결정
   2) 두 문자가 다른 경우, 이전 행 또는 이전 열의 값 중 더 큰 값을 현재 위치의 값으로 결정
4. DP[m-1][n-1]의 값이 최장공통부분수열의 길이
5. 배열을 역추적하며 최장공통부분수열 탐색
   현재 값과 왼쪽 값, 위쪽 값을 비교
   1) 현재 값과 왼쪽 값이 같은 경우, 왼쪽으로 이동
   2) 현재 값과 위쪽 값이 같은 경우, 위쪽으로 이동
   3) 그 외는 두 문자가 같은 경우이므로, 해당 문자 저장하고 왼쪽 위 대각선으로 이동
   행의 인덱스 또는 열의 인덱스가 범위를 벗어나면 반복 종료