[LCS] LCS with O(nlogn) LIS
LCS, Longest Common Subsequence : 가장 긴 공통된 부분 수열
두 수열에서 각각의 부분 수열 중, 서로 같은 부분 수열 중에서 가장 긴 부분 수열을 의미한다.
DP의 Well-known 유형 중 하나이다.
점화식
수열(문자열) S1, S2이 있다고 하자
S1의 길이는 N이고, S2의 길이가 M이고, i, j가 각각 S1, S2의 인덱스 일 때
int dp[N][M];
dp[i][j]는 S1을 i까지 S2를 j까지 봤을 때, 가장 긴 공통 부분 문자열의 길이
그냥 아래 표로 한 번 그려보는 것이 이해가 편하다.
즉 S1[i]와 S2[j]가 같다면, dp[i][j] = dp[i-1][j-1] + 1 이고, 값이 다르다면 dp[i][j] = max(dp[i][j-1], dp[i-1][j])
코드
- 기본
https://www.acmicpc.net/problem/9251 (LCS기본)
#include <iostream>
using namespace std;
string a, b;
int dp[1001][1001];
int main()
{
cin >> a >> b;
for (int i = 0; i < a.size(); ++i)
{
for (int j = 0; j < b.size(); ++j)
{
if (a[i] == b[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else {
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
}
}
}
cout << dp[a.size()][b.size()];
return 0;
}
- 경로 추적 (수열 구하기)
경로 추적의 경우, 역순으로 dp배열의 값을 비교하며 따라가면 된다.
https://www.acmicpc.net/problem/9252 (LCS경로추적)
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <cstring>
using namespace std;
string a, b;
int dp[1001][1001];
stack<char> path;
int main()
{
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
cin >> a >> b;
for (int i = 0; i < a.size(); ++i)
{
for (int j = 0; j < b.size(); ++j)
{
if (a[i] == b[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else {
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
}
}
}
cout << dp[a.size()][b.size()];
if (dp[a.size()][b.size()] <= 0) return 0;
cout << "\n";
int aIndex = a.size() - 1;
int bIndex = b.size() - 1;
while (aIndex >= 0 && bIndex >= 0)
{
if (a[aIndex] == b[bIndex])
{
path.push(a[aIndex]);
aIndex--;
bIndex--;
}
else if (dp[aIndex + 1][bIndex + 1] == dp[aIndex][bIndex + 1])
{
aIndex--;
}
else if (dp[aIndex + 1][bIndex + 1] == dp[aIndex + 1][bIndex])
{
bIndex--;
}
}
while (!path.empty())
{
cout << path.top();
path.pop();
}
return 0;
}
LIS, Longest Increasing Subsequence : 최장 증가 부분 수열
LIS, Longest Increasing Subsequence : 최장 증가 부분 수열 = 가장 긴 증가하는 부분 수열을 의미한다.
아래는 기본적인 LIS 코드로, O(N^2) 으로 LIS의 길이를 구할 수 있다. O(N^2)의 경우 점화식은 아래와 같다.
dp[i] = i 번째 수열에서의 LIS 길이
dp[i] = j 번째 값이 i 번째(현재) 값 보다 작다면, (j 번째 까지 봤을 때 LIS 길이 + 1) 가 dp[i] 보다 크다면 교체
https://www.acmicpc.net/problem/11053 (LIS 기본)
#include <iostream>
using namespace std;
int N;
int arr[1001];
int dp[1001];
int main()
{
cin >> N;
for (int i = 0; i < N; ++i) cin >> arr[i];
dp[0] = 1;
int answer = dp[0];
for (int i = 1; i < N; ++i) {
dp[i] = 1;
for (int j = i - 1; j >= 0; j--)
{
if (arr[i] > arr[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
answer = max(answer, dp[i]);
}
cout << answer;
return 0;
}
LIS O(NlogN)
이진 탐색 알고리즘을 사용하여, 모든 이전 부분 수열을 탐색할 필요 없이
logN 시간 복잡도로 들어갈 위치를 찾는 것으로 시간 복잡도 NlogN을 실현할 수 있다.
binary_search알고리즘을 직접 구현해도 되고, STL에서 lower_bound 함수를 지원하기 때문에 아래와 같이 간단하게 구현이 가능하다.
https://www.acmicpc.net/problem/12015 (LIS, NlogN)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int arr[1000001];
int dp[1000001];
int main()
{
cin >> N;
for (int i = 0; i < N; ++i) cin >> arr[i];
int end = 0;
dp[0] = -1;
for (int i = 0; i < N; ++i) {
if (arr[i] > dp[end]) {
//dp의 마지막 값 보다 현재 값이 더 크면
dp[++end] = arr[i];
}
else {
int* idx = lower_bound(dp, dp + end, arr[i]);
*idx = arr[i];
}
}
cout << end;
return 0;
}
STL Library 참고
1. binary_search(arr_begin, arr_end, find_value);
찾는 값이 존재하면, True, 아니면 False를 반환
2. lower_bound(arr_begin, arr_end, find_value);
찾는 값이 주어진 값보다 크거나 같으면서 제일 작은 값을 찾음, 없으면 구간의 끝 주소나 이터레이터를 반환
3. upper_bound(arr_begin, arr_end, find_value);
찾는 값이 주어진 값보다 크면서 제일 작은 값을 찾음, 없으면 구간의 끝 주소나 이터레이터를 반환
드디어, 최종적으로 O(NlogN) LCS 구현을 위한 준비가 끝났다.!
LCS의 경우 하나의 문자는 한 번만 나타나는 경우에 한해서만 O(NlogN) 로 문제를 해결 할 수 있다.
https://www.acmicpc.net/problem/13711 (LCS with LIS - O(NlogN))
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int A[100001];
int B[100001];
int index[100001];
int dp[100001];
int main()
{
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> A[i];
// 특정 값이 몇 번 인덱스인지 나타내는 index 배열, A 값에 따른 인덱스 배열로 치환
index[A[i]] = i;
}
int end = 0;
dp[0] = -1;
for (int i = 0; i < N; ++i) {
cin >> B[i];
// B 배열에는 해당 값의 인덱스를 저장
B[i] = index[B[i]];
if (dp[end] < B[i]) {
// 현재 값이 현재 LIS 값 보다 뒤에 있을 경우
dp[++end] = B[i];
}
else {
// dp 중 B[i] 보다 크거나 같은 값 중 가장 작은 값의 iter을 반환
int* idx = lower_bound(dp, dp + end + 1, B[i]);
*idx = B[i];
}
}
cout << end;
//for (int i = 0; i <= end; ++i) cout << dp[i] << " ";
return 0;
}
수열 A, B과 아래와 같을 때, A 기준으로 인덱스 치환을 한 B 배열과 결과(dp)배열
