n log n1 [C/C++] 백준 12015: 가장 긴 증가하는 부분 수열2 (O(logn) 알고리즘) ㅣ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 풀이! 이 문제를 기존의 11503: 가장 긴 증가하는 부분 수열 푼 방식으로 풀 경우에는 해결이 불가능하다. 그 이유는 11503 문제의 알고리즘은 시간복잡도가 O(n^2)로 구현해도 해결이 가능했지만 이 문제는 수열의 크기가 10^6이므로 똑같이 시간복잡도가 O(N^2)가 되어 시간초과가 발생하게 된다. 그렇기 때문에 새로운 아이디어를 생각해야한다. 일단 가장 기본적인 알고리즘은 11503 .. 2023. 10. 14. 이전 1 다음