Chapter 6 :: 이분탐색/LIS 알고리즘 이론

이분탐색

• O(N) ~ O(N²)으로는 절대 시간내에 풀 수 없는 탐색범위를 조건으로 가진 문제라면 이분탐색을 한 번쯤 생각해볼 수 있습니다. (e.g. 탐색해야 하는 N의 범위가 1억 이상이라던지…)
• 이분탐색은 (당연히) 정렬되거나 모든 값이 같은 값으로 초기화 된 배열에 대해 수행해야 합니다.
• C++에서 주로 사용되는 이분탐색 함수는 std::lower_bound(), std::upper_bound(), std::equal_range(), std::binary_search() 4가지가 있습니다.
• 이분탐색을 사용하는 경우는 탐색범위가 매우 큰 경우가 많습니다.
  • 그래서 int 범위를 넘는 경우가 많으므로 long long 또는 unsigned long long 자료형을 사용해야하는 경우가 많습니다.
  • typedef를 사용하거나, 모던 C++에서 권장하는 using문을 사용해서 ll 또는 ull 로 줄여 사용합시다.
• 이분탐색은 아래와 같은 구조를 사용합니다.

while (low <= high) {
    mid = low + (high - low) / 2;
    if (isAvailable(mid)) low = mid - 1;
    else high = mid + 1, ans = mid;
}

• 문제마다 isAvailable() 내용의 구현과 ans = mid 의 위치는 변경됩니다.

LIS (Longest Increasing Subsequence) 알고리즘

• LIS는 주어진 배열의 모든 요소가 오름차순으로 증가하는 부분배열들 중 가장 길이가 긴 부분배열을 의미합니다.
• LIS 관련 문제는 코딩테스트 출현 빈도는 낮습니다. 하지만, 아예 없는 것은 아니며, LIS는 찾는 방법을 알면 정말 빠르게 풀 수 있지만, 모른다면 정말 어렵기 때문에 알아두면 좋습니다.
• LIS 알고리즘 구조는 아래와 같습니다.

vector<int> lis(N, INF);
for (int i = 0; i < N; ++i) {
	auto pos = lower_bound(begin(lis), end(lis), 찾고자 하는 값);
	if (*pos == INF) len++;
	*pos = 찾고자 하는 값;
}