가장 긴 증가하는 부분 수열 문제

[Jinsun-Lee]

리드미

• 큰돌 6주차. 이분탐색과 LIS(최대증가부분수열)

[Jinsun-Lee]

추가 풀이한 문제 (리드미에 없음)

• ⭐11053. 가장 긴 증가하는 부분 수열, 14002. 가장 긴 증가하는 부분 수열 4: DP, O(N²)
• ⭐12015. 가장 긴 증가하는 부분 수열 2, 12738. 가장 긴 증가하는 부분 수열 3: lower_bound, O(NlogN)
  ⭐⭐14003. 가장 긴 증가하는 부분 수열 5: 역추적
• 11055. 가장 큰 증가하는 부분 수열, 11722. 가장 긴 감소하는 부분 수열, 11054. 가장 긴 바이토닉 부분 수열:

• ⭐2565. 전깃줄: LIS로는 안 풀어도 돼

[Jinsun-Lee]

완전탐색 O(2^N)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N; // 수열의 길이
vector<int> arr;
int mxlen = 0;

void DFS(int dep, vector<int>& path) {
    if (dep >= N) {
        if (path.size() > mxlen) mxlen = (int)path.size();
        return;
    }

    DFS(dep + 1, path);

    // 현재 원소 선택할 때, path가 비어있거나 or arr[dep]가 path의 마지막보다 작아
    if (path.empty() || path.back() < arr[dep]) {
        path.push_back(arr[dep]);
        DFS(dep + 1, path);
        path.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen_s(new FILE*, "input.txt", "r", stdin);

    cin >> N; 
    arr.resize(N);
    for (int i = 0; i < N; ++i) cin >> arr[i]; 
    
    vector<int> path = {};
    DFS(0, path);
    cout << mxlen;
    return 0;
}

[Jinsun-Lee]

가장 긴 증가하는 부분 수열 + 4(역추적)

- vector<int> dp(N, 1); // dp[i] = i번째 원소로 끝나는 LIS의 길이  
- int mxlen = 1; // 자기 자신만으로도 길이가 1이라서 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen_s(new FILE*, "input.txt", "r", stdin);

    int N; cin >> N;  // 수열의 길이
    vector<int> arr(N);
    for (int i = 0; i < N; ++i) cin >> arr[i]; 

    vector<int> dp(N, 1); // dp[i] = i번째 원소로 끝나는 LIS의 길이
    int mxlen = 1; // 자기 자신만으로도 길이가 1이라서 

    for (int i = 0; i < N; ++i) {
        // dp[i]는 나보다 앞에 있는 나를 마지막으로 두는 수열 중 최장 길이를 저장
        // 나보다 작은 애들을 돌면서 그숫자의최장길이+1이랑 지금길이랑 비교하며 갱신
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        mxlen = max(mxlen, dp[i]);
    }

    cout << mxlen;
    return 0;
}

    ...

    // (역추적 코드) 가장~수열1번의 dp 코드에서 아래 부분만 추가한 것
    vector<int> lis(mxlen);
    int cnt = mxlen;
    for (int i = N - 1; i >= 0; --i) {
        // 현재 길이랑 해당 원소까지의 lis길이가 같아
        if (cnt == dp[i]) lis[--cnt] = arr[i]; 
    }

    cout << mxlen << "\n";
    for (int i = 0; i < mxlen; ++i) cout << lis[i] << " ";
    return 0;
}

[Jinsun-Lee]

가장 긴 증가하는 부분 수열 2, 3 + 5(역추적)

2번이랑 3번 똑같은 코드로 정답ㅎ (dp랑 len 주의!!!)
풀이1: len 쓰는 코드(아래)
풀이2: len 대신 end까지 찾아서 메모리 더 쓰고 느린 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int N; cin >> N; 
    
    int x, len = 0; // 주의
    vector<int> dp(N, 0); // 주의

    for (int i = 0; i < N; ++i) {
        cin >> x;
        auto it = lower_bound(dp.begin(), dp.begin()+len, x); // dp[0..len)에서 x가 들어갈 수 있는 첫 번째 위치를 찾음
        if ((*it) == 0) ++len; // 그 위치가 아직 LIS 길이에 포함되지 않았음
        *it = x; // 찾은 위치에 x를 넣어, 길이가 같은 수열의 마지막 값을 최소화
    }

    cout << len;
    return 0;
}

6
10 20 10 30 15 50

10 20 30 50이 나오는지 확인!
역추적에서는 풀이2번 코드를 수정해서 풀었음

arr [10, 20, 10, 30, 15, 50] 입력값
dp  [10, 15, 30, 50]         LIS 길이 계산용

pos [0,  1,  0,  2,  1,  3 ] arr[i]가 dp 몇 번째에 들어갔는지
lis [10, 20, 30, 50]         실제 복원된 LIS

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen_s(new FILE*, "input.txt", "r", stdin);

    int N; cin >> N;
    vector<int> arr(N);

    int x, len = 0;
    vector<int> dp; // LIS 길이 계산용
    vector<int> pos(N); // arr[i]가 dp 몇 번째에 들어갔는지

    for (int i = 0; i < N; ++i) {
        cin >> x; arr[i] = x;
        auto it = lower_bound(dp.begin(), dp.end(), x); // 풀이 2번 코드

        int idx = it - dp.begin(); // 이 부분이 추가
        pos[i] = idx;

        if (it == dp.end()) dp.push_back(x); // if (it == (int)v.size()) 
        else *it = x;
    }

    len = dp.size(); // 


    // 역추적
    vector<int> lis(len); // 실제 복원된 LIS
    int cnt = len; // 현재 찾아야 하는 LIS의 위치(길이)
    for (int i = N - 1; i >= 0; --i) {
        if (cnt < 1) break; //
        if (cnt - 1 == pos[i]) lis[--cnt] = arr[i]; // 
    }

    cout << len << "\n";
    for (int i = 0; i < len; ++i) cout << lis[i] << " ";
    return 0;
}

[Jinsun-Lee]

역추적 틀린 코드

아... 당연함 lower_bound를 쓰는데 정렬도 안 되어 있어

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen_s(new FILE*, "input.txt", "r", stdin);

    int N; cin >> N;
    vector<int> arr(N);

    int x, len = 0;
    vector<int> dp(N, 0);

    for (int i = 0; i < N; ++i) {
        cin >> x; arr[i] = x;

        auto it = lower_bound(dp.begin(), dp.begin() + len, x); 
        if ((*it) == 0) ++len;
        *it = x; 
    }

    // 디버깅용: 10 15 30 50 
    for (int i = 0; i < len; ++i) cout << dp[i] << " ";
    cout << "\n";

    // 동일한 역추적 코드: 4, 0 0 0 0
    vector<int> lis(len);
    int cnt = len;
    for (int i = N - 1; i >= 0; --i) {
        if (cnt == dp[i]) lis[--cnt] = arr[i];
    }

    cout << len << "\n";
    for (int i = 0; i < len; ++i) cout << lis[i] << " ";
    return 0;
}

[Jinsun-Lee]

[Jinsun-Lee]

가장 큰 증가하는 부분 수열, 가장 긴 감소하는 부분 수열, 가장 긴 바이토닉 부분 수열

[Jinsun-Lee]

전깃줄

#include <iostream>
#include <algorithm>
using namespace std;

#define X first
#define Y second

pair<int, int> a[101]; // (x, y) = (왼쪽기둥, 오른쪽기둥)
int lis[101]; // LIS는 Y로 구함

int main() {
    freopen_s(new FILE*, "input.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);

    int N; cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> a[i].X >> a[i].Y;
    }

    sort(a, a + N);

    // X 1 2 3 4 6 7 9 10
    // Y 8 2 9 1 4 6 7 10

    int len = 0; // LIS의 길이 = 겹치지 않고 놓을 수 있는 전깃줄의 수
    for (int i = 0; i < N; ++i) {
        auto it = lower_bound(lis, lis + len, a[i].Y);
        if ((*it) == 0) ++len; // 이 위치에 값이 없으면 LIS 길이를 증가
        *it = a[i].Y; // LIS 후보 배열을 갱신
    }

    cout << N - len; // 제거하는 최소 전깃줄의 수
    return 0;
}

[Jinsun-Lee]

2568. 전깃줄 - 2

[Jinsun-Lee]

2995. 생일