이번에는 백준 11053번 가장 긴 증가하는 부분 수열 문제를 풀어보았습니다.
수열의 각 원소를 순회하면서 lis 배열을 관리하고, lower_bound()를 이용해 현재 값이 들어갈 위치를 찾아 LIS의 길이를 구하였습니다.
lis의 마지막 값보다 큰 숫자가 들어오면 뒤에 추가하고, 그렇지 않다면 현재 숫자 이상인 첫 번째 값을 현재 숫자로 교체하는 방식입니다.
문제 설명
수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구해야 합니다.
예를 들어
10 20 10 30 20 50이 주어졌다면 가장 긴 증가하는 부분 수열 중 하나는
10 20 30 50이고 길이는 4입니다.
여기서 부분 수열은 원래 수열의 순서를 유지해야 하며, 증가하는 부분 수열이므로 뒤의 값이 앞의 값보다 커야 합니다.
풀이 아이디어
lis라는 벡터를 하나 만들어 현재까지 확인한 숫자들을 이용해 LIS의 길이를 관리합니다.
새로운 숫자 num이 들어올 때마다
lower_bound(lis.begin(), lis.end(), num)을 이용합니다.
lower_bound()는 num 이상인 값이 처음 등장하는 위치를 반환합니다.
만약 그런 값이 존재하지 않는다면 현재 num이 lis의 모든 값보다 크다는 의미이므로 뒤에 추가합니다.
lis.push_back(num);반대로 num 이상인 값이 존재한다면 해당 값을 num으로 교체합니다.
*_pos = num;이렇게 하면 lis의 길이는 유지하면서 각 위치의 값을 최대한 작게 만들 수 있고, 이후 더 큰 숫자가 들어왔을 때 증가 부분 수열을 확장할 가능성을 높일 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> lis;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
for (int i=0; i<N; i++) {
int num;
cin >> num;
auto _pos = lower_bound(lis.begin(),lis.end(), num);
if (_pos == lis.end()) {
lis.push_back(num);
} else {
*_pos = num;
}
}
cout << lis.size();
return 0;
}
풀이 흐름
-
수열의 크기
N을 입력받습니다. -
숫자를 하나씩 입력받습니다.
-
lower_bound()를 이용해 현재 숫자 이상인 첫 번째 위치를 찾습니다. -
반환된 위치가
lis.end()라면 현재 숫자를lis의 마지막에 추가합니다. -
그렇지 않다면 해당 위치의 값을 현재 숫자로 교체합니다.
-
모든 숫자를 처리한 뒤
lis.size()를 출력합니다.
구현 포인트
1. lis 벡터의 역할
vector<int> lis;lis는 LIS의 길이를 효율적으로 구하기 위해 사용하는 벡터입니다.
lis[i]는 길이가 i + 1인 증가 부분 수열을 만들었을 때 가능한 마지막 값 중 작은 값을 유지하게 됩니다.
따라서 lis의 길이가 현재까지 만들 수 있는 LIS의 최대 길이가 됩니다.
다만 중요한 점은 최종적으로 만들어진 lis 자체가 반드시 원래 수열의 실제 LIS는 아니라는 것입니다.
이 문제에서는 실제 수열을 출력할 필요 없이 길이만 출력하면 되므로 lis.size()만 알면 충분합니다.
2. lower_bound를 이용한 위치 탐색
auto _pos = lower_bound(lis.begin(),lis.end(), num);lower_bound()는 정렬된 범위에서 num 이상인 첫 번째 원소의 위치를 반환합니다.
예를 들어 현재
lis = [10, 20, 40]이고
num = 30이라면 30 이상인 첫 번째 값은 40입니다.
따라서 _pos는 40의 위치를 가리키게 됩니다.
3. 현재 값이 가장 큰 경우
if (_pos == lis.end()) {
lis.push_back(num);
}lower_bound()의 결과가 lis.end()라는 것은 현재 lis에 num 이상인 값이 없다는 의미입니다.
즉,
lis의 모든 값 < num입니다.
따라서 현재 증가 부분 수열의 뒤에 num을 붙여 길이를 하나 늘릴 수 있습니다.
예를 들어
lis = [10, 20, 30]
num = 50이라면
lis = [10, 20, 30, 50]이 되면서 LIS의 길이가 3에서 4로 증가합니다.
4. 현재 값이 중간에 들어가는 경우
else {
*_pos = num;
}현재 값 이상인 원소가 존재한다면 해당 위치의 값을 현재 값으로 교체합니다.
예를 들어
lis = [10, 20, 50]
num = 30이라면 lower_bound()는 50의 위치를 반환합니다.
따라서
lis = [10, 20, 30]으로 변경됩니다.
LIS의 길이는 여전히 3이지만 마지막 값이 50에서 30으로 작아졌습니다.
마지막 값을 작게 유지할수록 이후에 더 많은 값을 뒤에 연결할 가능성이 커집니다.
5. 값을 교체해도 LIS의 길이가 유지되는 이유
값을 교체하는 것은 현재까지 발견한 LIS의 길이를 없애는 것이 아닙니다.
예를 들어
lis = [10, 20, 50]인 상황에서 30이 들어와
lis = [10, 20, 30]이 되었다면 길이 3의 증가 부분 수열을 만들 수 있다는 사실은 그대로입니다.
오히려 마지막 값이 더 작아졌기 때문에 이후 40 같은 값이 들어왔을 때
10 20 30 40처럼 더 긴 증가 부분 수열을 만들 수 있게 됩니다.
6. lower_bound를 사용하는 이유
증가하는 부분 수열에서는 같은 값을 연속해서 선택할 수 없습니다.
즉,
10 20 20 30에서 두 개의 20을 모두 LIS에 포함할 수 없습니다.
lower_bound()는 현재 숫자와 같거나 큰 첫 번째 값을 찾습니다.
따라서 같은 숫자가 들어오면 새로운 위치에 추가하지 않고 기존 위치를 교체합니다.
예를 들어
lis = [10, 20]
num = 20이라면 20의 위치를 찾아 다시 20으로 교체할 뿐 길이는 증가하지 않습니다.
이 때문에 문제에서 요구하는 엄격하게 증가하는 부분 수열을 처리할 수 있습니다.
7. lis가 항상 정렬된 상태로 유지되는 이유
lower_bound()를 사용하려면 탐색 대상이 정렬되어 있어야 합니다.
lis는 항상 오름차순 상태를 유지합니다.
현재 숫자 num 이상인 첫 번째 위치를 찾아 그 위치를 num으로 교체하기 때문입니다.
예를 들어
lis = [10, 30, 50]
num = 20이라면 30의 위치가 선택되고
lis = [10, 20, 50]이 됩니다.
앞의 10은 20보다 작고, 뒤의 50은 20보다 크기 때문에 정렬 상태가 유지됩니다.
8. 예제를 통한 과정
다음 수열을 확인해보겠습니다.
10 20 10 30 20 50처음 10이 들어오면 lis가 비어 있으므로 추가합니다.
[10]20은 모든 값보다 크므로 추가합니다.
[10, 20]다음 10은 lower_bound()를 통해 첫 번째 위치를 찾고 기존 10을 교체합니다.
[10, 20]30은 가장 크므로 추가합니다.
[10, 20, 30]다음 20은 기존 20의 위치를 교체합니다.
[10, 20, 30]마지막 50은 가장 크므로 추가합니다.
[10, 20, 30, 50]따라서 최종 lis.size()는 4가 됩니다.
9. 최종 정답
cout << lis.size();모든 원소를 확인한 후 lis의 크기가 가장 긴 증가하는 부분 수열의 길이가 됩니다.
이 문제에서는 실제 LIS를 복원할 필요가 없으므로 별도의 역추적 없이 lis.size()만 출력하면 됩니다.
시간복잡도
각 숫자마다 lower_bound()를 한 번 수행합니다.
lis의 최대 크기는 N이므로 한 번의 lower_bound()는
O(log N)의 시간이 필요합니다.
이를 N개의 숫자에 대해 수행하므로 전체 시간복잡도는
O(N log N)입니다.
lis에는 최대 N개의 값이 저장될 수 있으므로 공간복잡도는
O(N)입니다.
