[0626] 알고리즘

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를 구할 때 원소들을 비교하는 과정에서 쓰이지 않을까 예상했던 게 어느정도 맞았다. 정확히는

 

1. 입력 배열의 첫 번째 원소를 LIS 구할 배열에 넣어둔다.
2. 두 번째 원소부터 비교해나간다.
3. 만약 배열 속 원소가 LIS 배열의 마지막 원소보다 크면 그대로 LIS 배열 속에 넣는다.
4. 만약 작다면, 이분탐색을 이용해 해당 원소가 들어갈 자리를 정한다.
5. 최종적인 LIS 배열의 길이는 배열 속 원소의 개수.

  이분탐색을 오랜만에 봐서 전공 때 배웠던 내용을 참고했는데, 이건 배열에 들어갈 원소의 위치를 찾아주기 위한 탐색이라 그냥 이분탐색과는 모양이 좀 다르게 사용되었다. 알고 있는 내용을 알고리즘에 응용해서 쓴다는 건 아직 좀 어려운 것 같다... 그래도 LIS를 요 며칠간 계속 접해봐서 나름 이것저것 배울 수 있었다. 탐색도 다시 공부해야지...