linkedList를 이용한 LIS 역 추적, 백준 14003-가장 긴 증가하는 부분 수열 5 [C/C++]

https://www.acmicpc.net/problem/14003 

14003번: 가장 긴 증가하는 부분 수열 5

linkedList를 이용하여 Lis 역추적 문제를 풀어보겠습니다.

[본 글은 가장 긴 증가하는 부분 수열: o(n log n)를 알고있다고 가정합니다.]

 

완성된 코드:

#include <iostream>
#include <vector>
#include <algorithm>
#define endl        "\n"
#define inf     -2000000000
using namespace std;
struct node {
    int v;
    node* l;
};
void print(node n);
vector<int> output;
int c;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, idx = 0; cin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];
    vector<int> dp(n + 1, inf);
    vector<int> size(n + 1);
    dp.push_back(inf);
    for (int i = 0; i < n; i++) {
        int number = numbers[i];
        if (dp[idx] < number) {
            dp[++idx] = number;
            size[idx]++;
        }
        else {
            auto it = lower_bound(dp.begin(), dp.begin() + idx, number);
            *it = number;
            size[it - dp.begin()]++;
        }
    }
    cout << idx << endl;
    
    dp = vector<int>(n + 1, inf); // 다시 한 번 lis를 해야하니 dp를 초기화 해줍니다
    vector<node> trac[idx + 1]; // 모든 값을 표시할 dp입니다
    for (int i = 0; i <= idx; i++) trac[i] = vector<node>(size[i] * 2); // 에size보다 넉넉하게 메모리를 할당합니다
    vector<int> tracsize(idx + 1); // lis를 돌아갈 때, trac[]가 몇 번째 메모리까지 왔는지 체크합니다
    idx = 0;
 
    for (int i = 0; i < n; i++) {
        int number = numbers[i];
        if (dp[idx] < number) {
            dp[++idx] = number;
            trac[idx][++tracsize[idx]].v = number; // 값을 할당하고
            trac[idx][tracsize[idx]].l = new node; // 메모리를 부여하고
            trac[idx][tracsize[idx]].l = &trac[idx - 1][tracsize[idx - 1]]; // 참조한 이전의 값을 기억합니다
        }
        else {
            auto it = lower_bound(dp.begin(), dp.begin() + idx, number);
            int lo = it - dp.begin();
            *it = number;
            trac[lo][++tracsize[lo]].v = number; // 마찬가지입니다
            trac[lo][tracsize[lo]].l = new node;
            trac[lo][tracsize[lo]].l = &trac[lo - 1][tracsize[lo - 1]];
        }
    }
    output = vector<int>(idx);
   print(trac[idx][tracsize[idx]]); // 이 재귀함수로 lis값 부터 1 까지 추척하므로
    reverse(output.begin(), output.end()); // 뒤집어서 출력해 줍니다
    for (auto& iter: output) cout << iter << " "; cout << endl;
}
void print(node n) {
    output[c++] = n.v;
    if (n.l == NULL) return;
    print(*n.l);
}
 

 

코드 설명

#include <iostream>
#include <vector>
#include <algorithm>
#define endl        "\n"
#define inf     -2000000000
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, idx = 0; cin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];
    vector<int> dp(n + 1, inf);
    dp.push_back(inf);
    for (int i = 0; i < n; i++) {
        int number = numbers[i];
        if (dp[idx] < number) {
            dp[++idx] = number;
        }
        else {
            auto it = lower_bound(dp.begin(), dp.begin() + idx, number);
            *it = number;
        }
    }
    cout << idx << endl;
}

위 코드는 전형적인 Lis코드 입니다.

 

처음에는 lis코드의 dp를 출력하면 값이 나온다고 생각하여 위와 같은 코드를 작성하지만, dp와 실제 lis와는 전혀 상관이 없죠

 

예를 들어 3 1 4 6 2 0 3 6이 입력으로 주어진다면

Index	1	2	3	4	5	6	7
dp[Idx]	3

Index	1	2	3	4	5	6	7
dp[Idx]	1

Index	1	2	3	4	5	6	7
dp[Idx]	1	4

Index	1	2	3	4	5	6	7
dp[Idx]	1	4	6

Index	1	2	3	4	5	6	7
dp[Idx]	1	2	6

---

Index	1	2	3	4	5	6	7
dp[Idx]	0	2	3	6

 

해서

dp[Idx]

0

2

3

6

 

결국 답이 아닌 이상한 값을 출력하게 됩니다.

 

이 문제를 해결하기 위해서 일반적인 방법으로는 dp의 값을 입력값에다가 기억해 두는 것입니다.

Input	3	1	4	6	2	0	3	6
dp[Idx]	1

3은 dp 값이 1이니까 1을

Input	3	1	4	6	2	0	3	6
dp[Idx]	1	1

1의 dp 값이 1이니까 1을

Input	3	1	4	6	2	0	3	6
dp[Idx]	1	1	2

4의 dp 값이 2이니까 2를

Input	3	1	4	6	2	0	3	6
dp[Idx]	1	1	2	3

6의 dp값이 3이니까 3을, 이렇게 계속 진행하게 되면

---

Input	3	1	4	6	2	0	3	6
dp[Idx]	1	1	2	3	2	1	3	4

다음과 같은 배열이 나옵니다.

 

위 케이스의 가장 긴 증가하는 부분 수열의 값은 4입니다. 그러므로

위와 같이 dp[Idx]가 1인 구간 부터 탐색하면!

코드:

#include <iostream>
#include <vector>
#include <algorithm>
#define endl        "\n"
#define inf     -2000000000
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, idx = 0; cin >> n;
    vector<int> numbers(n);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];
    vector<int> dp(n + 1, inf);
    dp.push_back(inf);
    for (int i = 0; i < n; i++) {
        int number = numbers[i];
        if (dp[idx] < number) {
            dp[++idx] = number;
            ans[i] = idx;
        }
        else {
            auto it = lower_bound(dp.begin(), dp.begin() + idx, number);
            *it = number;
            ans[i] = it - dp.begin();
        }
    }
    cout << idx << endl;
    
    int tmp = 1;
    for (int i = 0; i < n; i++) {
        if (ans[i] == tmp) {
            cout << numbers[i] << " "; 
            tmp++;
        }
    }
}

 

 

 

---

그러나 우리의 목표는 linkedList로 문제를 푸는 것이죠

 

아이디어는 처음에 실패했던 dp를 이용하는 방법입니다.

Index	1	2	3	4	5	6	7
dp[Idx]	3

Index	1	2	3	4	5	6	7
dp[Idx]	1

Index	1	2	3	4	5	6	7
dp[Idx]	1	4

Index	1	2	3	4	5	6	7
dp[Idx]	1	4	6

Index	1	2	3	4	5	6	7
dp[Idx]	1	2	6

---

Index	1	2	3	4	5	6	7
dp[Idx]	0	2	3	6

여기 dp[Idx]를 나타낼땐 이후에 나오는 값이 기존의 dp[Idx]보다 작을 때 무조건 바꾸었죠

하지만 바꾸지 말고 다 기억한다면 어떻게 될까요?

 

Index	1	2	3	4	5	6	7
dp[Idx][]	3

Index	1	2	3	4	5	6	7
dp[Idx][]	3
	1

Index	1	2	3	4	5	6	7
dp[Idx][]	3	4
	1

Index	1	2	3	4	5	6	7
dp[Idx][]	3	4	6
	1

Index	1	2	3	4	5	6	7
dp[Idx][]	3	4	6
	1	2

---

Index	1	2	3	4	5	6	7
dp[Idx][]	3	4	6	6
	1	2	3
	0

결국엔 이와 같은 2차원 dp[Idx][i]를 만들 수 있습니다.

---

하지만 이 2차원 배열로는 답을 나타내지 못합니다.

dp 값이 어떤 값을 참조하여 나왔는지를 알아야 역추적하여 lis를 나타낼 수 있습니다

방금 위에 테이블을 가져와서 화살표를 표시해보죠

6은 1 - 4와 연결되어 있다

6을 보았을 때 기존 dp로 출력했더라면 6이 참조한 4가 아니라 가장 작은 값인 2를 출력했을 것입니다.

그러나 6이 무엇을 참조하였는지를 표시한다면 2를 출력하지 않죠

 

모두다 표시하였을 때(일부 중복 무시)

자 그렇다면 코드로 나타내 볼려고 하는데...!

 

input이 1,000,000 입니다. 2차원 dp를 나타낸다면 메모리가 1,000,000^2를 요구하게되어 너무 많은 메모리를 참조하게 되죠

그래서 먼저 lis로 구할 때, dp의 size를 조정해 줘야 합니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl        "\n"
#define inf     -2000000000
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, idx = 0; cin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];
    vector<int> dp(n + 1, inf);
    vector<int> size(n + 1);
    dp.push_back(inf);
    for (int i = 0; i < n; i++) {
        int number = numbers[i];
        if (dp[idx] < number) {
            dp[++idx] = number;
            size[idx]++; // 각 idx에 몇 개의 값이 들어가는 가?
        }
        else {
            auto it = lower_bound(dp.begin(), dp.begin() + idx, number);
            *it = number;
            size[it - dp.begin()]++; // 각 idx에 몇 개의 값이 들어가는 가?
        }
    }
    cout << idx << endl;
}

이렇게 얻은 size[]로 dp에 메모리를 부여한다면 메모리를 초과하지 않고 2차원으로 표시할 수 있습니다. 

메모리는 1,000,000 ^2가아니라 1,000,000만 사용하니까요

---

이제 메모리 문제는 해결하였습니다. 그렇다면 참조한다는 것을 어떻게 표시할까요?

 

struct node {
   int v; // 값
   node* l; // 참조한 값의 주소를 저장한다
};

드디어 나오는 링크드 리스트죠. 간단한 링크드리스트를 만들어 참조한 값의 주소를 저장해 줍시다

 

그래서 코드를 완성한다면 아래와 같은 코드가 될 것입니다

 

코드:

#include <iostream>
#include <vector>
#include <algorithm>
#define endl        "\n"
#define inf     -2000000000
using namespace std;
struct node {
    int v;
    node* l;
};
void print(node n);
vector<int> output;
int c;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, idx = 0; cin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];
    vector<int> dp(n + 1, inf);
    vector<int> size(n + 1);
    dp.push_back(inf);
    for (int i = 0; i < n; i++) {
        int number = numbers[i];
        if (dp[idx] < number) {
            dp[++idx] = number;
            size[idx]++;
        }
        else {
            auto it = lower_bound(dp.begin(), dp.begin() + idx, number);
            *it = number;
            size[it - dp.begin()]++;
        }
    }
    cout << idx << endl;
    
    dp = vector<int>(n + 1, inf); // 다시 한 번 lis를 해야하니 dp를 초기화 해줍니다
    vector<node> trac[idx + 1]; // 모든 값을 표시할 dp입니다
    for (int i = 0; i <= idx; i++) trac[i] = vector<node>(size[i] * 2); // 에size보다 넉넉하게 메모리를 할당합니다
    vector<int> tracsize(idx + 1); // lis를 돌아갈 때, trac[]가 몇 번째 메모리까지 왔는지 체크합니다
    idx = 0;
 
    for (int i = 0; i < n; i++) {
        int number = numbers[i];
        if (dp[idx] < number) {
            dp[++idx] = number;
            trac[idx][++tracsize[idx]].v = number; // 값을 할당하고
            trac[idx][tracsize[idx]].l = new node; // 메모리를 부여하고
            trac[idx][tracsize[idx]].l = &trac[idx - 1][tracsize[idx - 1]]; // 참조한 이전의 값을 기억합니다
        }
        else {
            auto it = lower_bound(dp.begin(), dp.begin() + idx, number);
            int lo = it - dp.begin();
            *it = number;
            trac[lo][++tracsize[lo]].v = number; // 마찬가지입니다
            trac[lo][tracsize[lo]].l = new node;
            trac[lo][tracsize[lo]].l = &trac[lo - 1][tracsize[lo - 1]];
        }
    }
    output = vector<int>(idx);
   print(trac[idx][tracsize[idx]]); // 이 재귀함수로 lis값 부터 1 까지 추척하므로
    reverse(output.begin(), output.end()); // 뒤집어서 출력해 줍니다
    for (auto& iter: output) cout << iter << " "; cout << endl;
}
void print(node n) {
    output[c++] = n.v;
    if (n.l == NULL) return;
    print(*n.l);
}

링크드리스트 + 다이나믹프로그래밍 + 이분탐색