목록프로그랠밍 (1)

algoqna

[BOJ 12015] 가장 긴 증가하는 부분수열 2

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열의 크기가 1,000,000으로 가장 쉬운 방법인 O(n^2)의 방식으로 증가수열의 길이를 구하기에는 시간초과가 나는 문제입니다. 따라서 최소 O(NlogN)로 동작하는 알고리즘을 설계해야 합니다. 이분탐색을 이용하여 증가수열의 길이를 구하는 방식이 존재합니다. 단, 이 방식으로는 수열의 길이만 알 수 있고 수열은 알 수 없습니다. 물론, 수열을 알고 싶다면 추가로 수정을 하면 됩니다. 우선 문제의 예시로 증가수열을 설명하겠습니다. 10 20 10 30 20 ..
프로그래밍/기타 문제풀이 2022. 11. 9. 18:32
이전 Prev 1 Next 다음