[백준 12015번] 가장 긴 증가하는 부분 수열 2 (C++, Python)

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

이번 포스트에서는 이전 포스트에서 설명한 LIS 문제(11053번)의 심화 문제인 가장 긴 증가하는 부분 수열 2 를 포스트하도록 하겠습니다.

 

해당 문제는 solved.ac 기준 골드 2에 위치한 문제입니다.

 

먼저 문제입니다.

이전 문제와 똑같이 수열의 크기 N과 수열 A가 주어지고, 이때 수열 A에서 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제입니다.

 

단, 시간제한이 1초에 N이 1000000 까지 주어지므로, 이전 문제처럼 DP 점화식으로 해결하기에는 O(N^2)의 시간복잡도를 소요하므로, 문제를 해결할 수 없습니다.

 

LIS는 결국 오름차순을 유지하기 때문에 해당 문제는 LIS를 만드는 과정에서 이진 탐색을 사용하여 O(n log n)의 시간복잡도로 해결합니다.

 

입력을 받을 때 마다, 현재 arr 배열의 마지막값과의 비교로 크다면, 다음 인덱스에 입력받은 값을 추가하고, 그렇지 않다면, 이진 탐색을 통해 입력받은 값보다 크면서 차이가 가장 적은 인덱스 위치의 값을 입력받은 값으로 치환합니다.

 

예제를 보고 글로 작성한 LIS와 내부 값들은 다르게 출력될 수 있으나, 결국 작은 값을 계속해서 치환하면서 오름차순 배열을 만들기 때문에 현재 수열에서 가장 긴 수열을 만들어냅니다. 그렇게 하여 길이값을 출력하는 원리로 작성하면 되겠습니다.

 

다음은 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
int binarySearch(int* arr, int start, int last, int target) {
    int mid;
 
    while(start < last) {
        mid = (start + last) / 2;
        if(arr[mid] < target)
            start = mid + 1;
        else
            last = mid;
    }
    return start;
}
 
int main() {
    int n, tmp, idx = 0;
    cin >> n;
 
    int arr[n];
    
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        if(i == 0)    arr[0] = tmp;
 
        if(arr[idx] < tmp)
            arr[++idx] = tmp;
        else
            arr[binarySearch(arr,0,idx,tmp)] = arr;
    }
    cout << idx + 1;
    return 0;
}

다음은 Python 코드입니다.

 

def binarySearch(arr, start, end, target) :
    mid = 0
 
    while(start < end) :
        mid = (start + end) // 2
        if(arr[mid] < target) :
            start = mid + 1
        else :
            end = mid
    return start
 
n = int(input())
idx = 0
extra = list(map(int,input().split()))
arr = [0] * n
 
for i in range(n) :
    if i == 0 :
        arr[0] = extra[0]
 
    if extra[i] > arr[idx] :
        idx += 1
        arr[idx] = extra[i]
    else :
        arr[binarySearch(arr,0,idx,extra[i])] = extra[i]
 
print(idx + 1)

해당 문제는 DP 알고리즘을 이진 탐색을 통해 최적화 하는 문제로, LIS가 오름차순으로 정렬이 되어 있다는 점을 이용하여 이진탐색을 생각할 수 있다면 코드의 작성 자체는 어렵지 않은 문제였습니다.

다음 포스트에서 또 다른 백준 알고리즘 문제로 포스트하도록 하겠습니다. 감사합니다.