최장 증가 부분 수열 + 역추적

최장 증가 부분 수열의 구성요소를 구하라고 한다면

역추적을 통해 구해야한다.

 

왜냐하면 DP 배열 자체가 구성요소 순서를 제대로 보장해주지 않기 때문이다!

 

 

핵심은 최장 증가 부분 수열을 구성하는 마지막 원소부터

rank를 줄이면서 앞으로 오면서 직전 값을 찾는 것이다.

 

---

[최장 증가 부분 수열 구성 원소 찾기]

 

1. O(N^2) 방식

 

O(N^2) DP 방식은 최장 증가 수열 길이만 표시하는 것이기 때문에 구성원소를 찾으려면

따로 구성원소 역추적을 위한 메모를 해놔야한다.

    int dp[SIZE];
    for (int i = 0; i < N; i++)
    {
        dp[i] = 1;
    }

    int max_len = 1;
    int start_idx = 0;
    for (int i = 1; i < N; i++)
    {
        for (int k = 0; k < i; k++)
        {
            if (arr[i] > arr[k])
            {
                dp[i] = max(dp[i], dp[k] + 1);
                if (dp[i] > max_len)
                {
                    max_len = dp[i];
                    start_idx = i;
                }
            }
        }
    }

    vector<int> ans;
    int rank = max_len;
    for (int i = start_idx; i >= 0; i--)
    {
        if (dp[i] == rank)
        {
            ans.push_back(arr[i]);
            rank--;
        }
    }

    reverse(ans.begin(), ans.end());

 

2. O(N*logN) 방식

 

이진탐색을 활용하여 최장 증가 부분 수열의 길이는 구할 수 있어도,

그 최장증가부분수열을 구성하는 구성요소 배열을 찾기 위해서는 추가적인 방법이 필요하다.

 

LIS를 찾기 위해 DP를 돌리는 과정에서 LIS 배열은 매 턴마다 오염되기 때문이다.

 

[10, 20, 30, 5, 6]

1. 10, 20, 30 까지 넣으면 dp = [10, 20, 30] 이 된다.

2. 그 다음 5를 넣으면? 10 자리를 뺏고 dp = [5, 20, 30]이 된다.

3. 그 다음 6을 넣으면? 20의 자리를 뺏고 dp = [5, 6, 30]이 된다.

 

결과적으로 배열에는 [5, 6, 30]이 남는다.

하지만 원래 수열에는 [5, 6, 30] 이라는 순서의 부분수열은 존재하지 않는다.

 

따라서 따로 역추적을 위한 자기 직전 노드를 기록하여 마지막에 역추적을 통해 구성원소를 찾아주어야한다.

 

    for (int i = 0; i < N; i++)
    {
        int idx = binary_search(arr[i]);

        if (idx == v.size())
        {
            v.push_back(arr[i]);
        }
        else
        {
            v[idx] = arr[i];
        }
        pos[i] = idx;
    }

    int cur = v.size() - 1;
    vector<int> ans;
    for (int i = N - 1; i >= 0; i--)
    {
        if (pos[i] == cur)
        {
            ans.push_back(arr[i]);
            cur--;
        }
    }

    reverse(ans.begin(), ans.end());