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

문제설명

문제를 살펴보면 이전에 풀이하였던 문제(11053)과 동일한듯 하나, 수열 A의 크기가 1,000에서 1,000,000으로

늘어난 상태이다 따라서 이전에 풀이하였던 방식으로 작성할 경우 시간 초과 또는 메모리 초과가 발생할 수 있다

해당 문제를 어떻게 풀이를 하였나 살펴보니 동적 프로그래밍으로 작성한 사람도 많았지만,

필자의 제출 풀이 코드를 확인해보니 이분 탐색을 사용하여 해결한 코드를 사용하였다 대신

직접 이분 탐색 함수를 구현하지는 않았고, 파이썬에 이미 정의된 from bisect import bisect_left를 사용하였다

그래서 이분 탐색을 연습하는 목적이므로 직접 이분 탐색 함수를 구현하여 코드를 작성하였다

 

C++로 코드를 작성함에 앞서, 문제에서 주어진 최대 크기를 기준으로 배열을 두 개 만들어주었다

하나는 수열 A, 하나는 부분 수열을 저장하기 위한 배열 result를 선언하였다

이후 로직은 이전에 풀이함과 동일한데, 간단하게 설명하자면 수열의 처음부터 확인하며 값을 부분 수열에 저장한다

증가하는 수열을 만들기 때문에 result의 마지막 index의 값보다 더 큰 경우 해당 값을 result에 계속 삽입한다

만약 result의 마지막 index보다 값이 더 작은 경우에는 다르게 처리해야하는데, 이는 예시로 설명하겠다

 

10 20 30 이라는 값이 result에 저장되어있을때, 다음에 확인한 값이 15라면 10 15 30 으로 대체한다

해당 과정이 필요한 이유는 최대한 길이가 긴 증가하는 부분 수열(LIS)을 유지하면서도, 더 작은 값으로

대체하여 이후 더 많은 원소를 추가할 수 있도록 하기 위해서이다 

해당 위치를 찾기 위해 이분 탐색을 사용하게 되고, 이를 반복하며 cnt 변수에는 최대 길이가 저장되게 된다

#include <iostream>
using namespace std;
#define MAXSIZE 1000001

int binary_search(int start, int end, int target, int res[]) {
    int mid;
    while(start < end) {
        mid = (start + end) / 2;
        if(res[mid] < target)
            start = mid + 1;
        else
            end = mid;
    }
    return end;
}

int main() {
    int size;
    int A[MAXSIZE] = {};
    cin >> size;
    for(int i = 0; i < size; i++)
        cin >> A[i];
    
    int result[MAXSIZE] = {};
    int cnt = 1;
    result[0] = A[0];
    for(int i = 0; i < size; i++) {
        if(result[cnt-1] < A[i]) {
            result[cnt] = A[i];
            cnt++;
        } else {
            int idx = binary_search(0, cnt-1, A[i], result);
            result[idx] = A[i];
        }
    }

    cout << cnt << endl;

    return 0;
}

이를 파이썬으로 작성하면 다음과 같다(연습을 위해 직접 이분 탐색 함수를 구현하였다)

import sys
input = sys.stdin.readline

def binary_search(start, end, target, res):
    while start < end:
        mid = (start + end) // 2
        if res[mid] < target:
            start = mid + 1
        else:
            end = mid
    return end

size = int(input()) 
A = list(map(int, input().split()))

result = [A[0]]
cnt = 1
for i in range(size):
    if result[cnt-1] < A[i]:
        result.append(A[i])
        cnt += 1
    else:
        idx = binary_search(0, cnt - 1, A[i], result)
        result[idx] = A[i]
        
print(cnt)