문제 링크
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
어제 풀어봤던 11053번: 가장 긴 증가하는 부분 수열 문제에 이어서 2번째 문제입니다.
이전 문제는 \(O(N^2)\) 의 시간복잡도로 풀 수 있었지만, 이번 문제부터는 \(O(N \log N)\) 의 시간복잡도로 해결해야합니다!
차근차근 해결방법을 설명하며 풀이해보겠습니다.
풀이
LIS문제를 DP+이분탐색으로 풀이하면 됩니다.
이 문제에서는 이전 문제와는 다르게, N의 범위가 100만까지로 무지막지하게 큽니다.
N의 크기가 크기 때문에, \(O(N^2)\) 으로는 해결이 불가능하고 \(O(N \log N)\)으로 해결을 봐야합니다.
이전에 풀었던 방식과는 풀이가 거의 비슷하지만 다시 설명해보겠습니다.
저는 3개의 배열을 이용해서 알고리즘을 진행했습니다.
- arr : 초기에 주어진 입력 배열
- seq : 가장 긴 수열의 값을 저장하는 (벡터) 배열
- dp : 값을 처음부터 비교해봤을 때 가장 긴 수열의 길이를 저장하는 배열
초기상태의 seq[0]의 값은 arr[i], dp[0] 값은 1이며, 앞으로 저장될 dp의 값들은 모두 1이 베이스가 됩니다.
왜냐하면 자기 자신만 존재하는 수열(예: {10}, {20})이 수열의 부분집합의 가장 작은 길이가 될 것이기 때문입니다.
dp[1]부터는 차례로 뒤에 있는 수들과 나의 수를 비교해보며 값이 자신보다 작으면서 + 길이가 가장 긴 값을 찾아냅니다.
찾아낼 때, seq 배열이 항상 오름차순임을 이용하여 이분탐색을 사용합니다. 찾아낸 뒤, 값과 길이를 각각 seq와 dp 배열에 저장합니다.
arr배열을 모두 돌리면 seq배열의 크기가 이 문제의 답이 될 것입니다.
풀이코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int arr[1000001];
int dp[1000001];
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
vector<int> seq;
seq.push_back(arr[0]);
dp[0] = 1;
for (int i = 1; i < n; i++) {
if (seq.back() < arr[i]) {
seq.push_back(arr[i]);
dp[i] = seq.size() - 1;
} else {
int st = 0;
int en = seq.size() - 1;
while (st < en) {
int mid = (st + en) / 2;
if (arr[i] > seq[mid]) st = mid + 1;
else en = mid;
}
dp[i] = en;
seq[en] = arr[i];
}
}
cout << seq.size();
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(false);
cin.tie(0);
#endif
solve();
return 0;
}1
배운점
- LIS를 이분탐색으로 해결하는 방법을 배울 수 있었습니다.
- 이분탐색을 복습할 수 있었습니다.
부족한 글 봐주셔서 감사합니다. 🙇
풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!
'Study > 알고리즘 풀이' 카테고리의 다른 글
[백준] 11049번: 행렬 곱셈 순서 (C++) (2) | 2023.08.19 |
---|---|
[백준] 18353번: 병사 배치하기 (C++, LIS 풀이) (0) | 2023.08.18 |
[백준] 11053번: 가장 긴 증가하는 부분 수열 (java) (0) | 2023.08.16 |
[백준] 1647번: 도시 분할 계획 (C++) (0) | 2023.08.14 |
[백준] 1766번: 문제집 (C++) (0) | 2023.08.10 |