[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) 로 문제를 해결 할 수 있다.

LCS4 - 13711 번

 

 

 

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)배열

dp[end] : B[i]