백준/가장 긴 증가하는 부분 수열
-
백준 14003 nodejs백준/가장 긴 증가하는 부분 수열 2023. 2. 1. 14:02
문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 이분 탐색을 이용해 오름차순으로 정렬된 A의 부분 배열인 B를 만든다. B의 값이 바뀔 때마다 index와 값을 C에 저장한다. C를 역순으로 순회하면서 B 값을 변경해준다. let [[N], A] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => e.split..
-
백준 12015 nodejs백준/가장 긴 증가하는 부분 수열 2022. 12. 19. 15:23
문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 LIS를 활용한다. 이분 탐색을 사용하여 시간 복잡도를 O(NlogN)으로 줄인다. (참조한 블로그) let [n, I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => e.split(' ').map(Number)) n = +n const A = [] for (let i = 0; i < n..