수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
6
10 20 10 30 20 50
4
lis
배열은 현재까지의 LIS를 저장하는 배열이다. 원소를 하나씩 순회하면서 현재 원소(arr[i]
)가 lis
의 마지막 원소보다 크다면 그대로 추가한다. 그렇지 않다면 이진 탐색을 사용하여 lis
배열에 삽입할 위치를 찾는다.O(N*log(N))
으로 해결할 수 있다.✅ 답안
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input[1].split(' ').map(Number);
const lis = [arr[0]]; // LIS를 저장하는 배열 초기화
for (let i = 1; i < N; i++) {
if (arr[i] > lis[lis.length - 1]) {
// 현재 원소가 LIS의 마지막 원소보다 크면 추가
lis.push(arr[i]);
} else {
// 아니라면 이진 탐색을 사용하여 적절한 위치에 삽입
let start = 0;
let end = lis.length - 1;
while (start < end) {
const mid = Math.floor((start + end) / 2);
if (lis[mid] < arr[i]) {
start = mid + 1;
} else {
end = mid;
}
}
lis[end] = arr[i];
}
}
console.log(lis.length);