12015. 가장 긴 증가하는 부분 수열 2
저번에 풀었던 문제와 똑같지만 조건이 틀리다. 저번건 수열 크기(N)의 조건이 1 ≤ N ≤ 1,000 이었는데, 이번 문제는 1 ≤ N ≤ 1,000,000 이다. 따라서 저번에 쓴 O(N^2) 방식을 사용하면 시간 초과가 난다.
보니 이분 탐색을 사용하라는 것 같아서 오랜만에 또 자료구조 책을 뒤졌다. 대충의 느낌은 오는데 구체적으로 어떻게 해야할지 잘 모르겠어서 머리를 굴려보다 최종적으로는 서치를 해서 풀었다...
#include <iostream>
#include <algorithm>
#include <vector>
int binarySearch(int left, int right, int item);
int num[1000001];
int lis[1000001];
int main()
{
std::cin.tie(NULL);
std::ios_base::sync_with_stdio(false);
int n;
std::cin >> n;
for (int i = 0; i < n; i++)
{
std::cin >> num[i];
}
lis[0] = num[0];
int j = 0;
for (int i = 1; i < n; i++)
{
if (lis[j] < num[i])
{
lis[j + 1] = num[i];
j++;
}
else
{
lis[binarySearch(0, j, num[i])] = num[i];
}
}
std::cout << j + 1 << '\n';
return 0;
}
int binarySearch(int left, int right, int item)
{
int mid;
while (left < right)
{
mid = (left + right) / 2;
if (lis[mid] < item)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return right;
}
이분탐색은 원래 정렬이 되어있는 목록에서 찾고자 하는 원소를 찾아낼 때 사용하는 걸로 알고 있는데, 주어진 데이터셋을 정렬할리는 없을 거고... 대충 LIS를 구할 때 원소들을 비교하는 과정에서 쓰이지 않을까 예상했던 게 어느정도 맞았다. 정확히는
- 입력 배열의 첫 번째 원소를 LIS 구할 배열에 넣어둔다.
- 두 번째 원소부터 비교해나간다.
- 만약 배열 속 원소가 LIS 배열의 마지막 원소보다 크면 그대로 LIS 배열 속에 넣는다.
- 만약 작다면, 이분탐색을 이용해 해당 원소가 들어갈 자리를 정한다.
- 최종적인 LIS 배열의 길이는 배열 속 원소의 개수.
이분탐색을 오랜만에 봐서 전공 때 배웠던 내용을 참고했는데, 이건 배열에 들어갈 원소의 위치를 찾아주기 위한 탐색이라 그냥 이분탐색과는 모양이 좀 다르게 사용되었다. 알고 있는 내용을 알고리즘에 응용해서 쓴다는 건 아직 좀 어려운 것 같다... 그래도 LIS를 요 며칠간 계속 접해봐서 나름 이것저것 배울 수 있었다. 탐색도 다시 공부해야지...
'공부 > 알고리즘' 카테고리의 다른 글
[~0718] 알고리즘 (0) | 2021.07.19 |
---|---|
[0629] 알고리즘 (0) | 2021.06.30 |
[0625] 알고리즘 (0) | 2021.06.26 |
[0624] 알고리즘 (0) | 2021.06.25 |
[0622] 알고리즘 (0) | 2021.06.23 |