[바미] 가장 긴 증가하는 부분 수열 2

문제

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

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0]);
const A = input[1].split(' ').map(Number);

function lengthOfLIS(A) {
    const lis = [];

    for (let num of A) {
        if (lis.length === 0 || lis[lis.length - 1] < num) {
            lis.push(num);
        } else {
            let low = 0;
            let high = lis.length - 1;
            while (low < high) {
                const mid = Math.floor((low + high) / 2);
                if (lis[mid] < num) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            lis[low] = num;
        }
    }

    return lis.length;
}

const result = lengthOfLIS(A);
console.log(result);

문제 해설

이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence)을 찾는 문제입니다. 

LIS를 찾기 위해 여러 가지 방법이 있지만, 이 문제에서는 시간 제한이 있어 이진 탐색을 활용한 O(N log N) 알고리즘을 사용하여 풀었습니다.

 

동적 계획법(DP)와 이진 탐색을 활용하여 각 원소를 처리할 때마다 현재까지의 LIS를 유지하였고, 이진 탐색을 활용하여 LIS를 효율적으로 업데이트하는 코드입니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

이 접근 방법은 각 원소에 대해 이진 탐색을 수행하므로 시간 복잡도는 𝑂(𝑁 log⁡ 𝑁)입니다. 

여기서 𝑁은 수열의 길이를 의미합니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

공간 복잡도는 LIS를 저장하는 데 필요한 𝑂(𝑁)입니다. 

이 외에 추가적인 메모리가 거의 필요하지 않기 때문에 전체 공간 복잡도는 𝑂(𝑁)이 됩니다.