✅ 최장 공통 부분 수열 LCS
LCS(Longest Common Subsequence)는 주로 최장 공통 부분수열을 나타내지만 최장 공통 문자열을 말하기도 한다.
- 최장 공통 문자열은 반드시 부분 문자열이 연결된 형태여야 한다. banana, vbankn
- 최장 공통 부분 수열은 떨어져 있어도 상관없다. bdanvv, vbkkanm
최장 공통 부분 수열는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다.
1-1. LCS 길이 찾는 방법(DP)
이중 포문을 사용하여 각 원소들을 하나씩 직접 비교해주면서 dp값을 갱신해주면 된다.
dp는 2차원 배열로 수열 n1과 n2의 LCS길이를 저장해준다.
dp[수열n1의 i번째][수열 n2의 j번째] = 수열 n1과 수열 n2의 LCS의 길이
- 설계
i: str1의 i번째 문자
j: str2의 j번째 문자
1. if(i==j) : str1(0~i-1) 과 str(0~j-1)의 LCS+1
2. if(i!=j) : dp[i-1][j] 와 dp[i][j-1]중 최댓값 받아오기.
1-2. LCS 문자열 찾는 방법 (DP)
위에서 사용한 dp 2차원 배열 표를 보면 쉽게 풀어낼 수 있다. 위의 색칠된 숫자를 자세히 보면 dp값이 변하는 부분임을 알 수 있다. 그 부분이 LCS를 찾아내는 부분이므로 저 위치들만 골라서 탐색을 해주면 된다.
설계
dp값이 줄어드는 절벽 구간에 도달했다면 해당 부분에 속하는 문자를 저장한다. n->0하향식으로 값을 저장해주므로 후입선출을 해주는 Stack 자료구조를 사용하여 데이터를 저장한다.
1. dp[i][j] == dp[i-1][j] 이면 i->i-1, j->j
2. dp[i][j] == dp[i][j-1] 이면 i->i,j->j-1
3. 1,2가 아니면 해당 부분은 절벽 구간!! => stack저장
- stack.push(str.charAt(i-1));
- i->i-1,j->j-1
✅ LCS 길이 찾는 방법 (이진탐색 LIS)
위의 DP 풀이는 이중 포문을 사용한 풀이로 두 수열 길이가 n1, n2라고 할때 시간복잡도 O(n^2) 을 갖게 된다. 이는 문자열 길이가 100만 이상으로 주어지면 엄청난 시간이 걸릴 것이다.
이 두 수열은 LCS길이를 이중 포문이 아닌 LIS를 통해 LCS를 구할 수 있는 방법이 있다.
- 하나의 배열을 기준 index로 정하고 다른 배열은 기준 index를 통해 다시 원소를 재배열한 다음 해당 배열의 LIS를 구하면 결국은 두 배열의 LCS를 찾는 것과 똑같다.
