오름세
-
백준 3745번 오름세 [LIS] :: 마이구미알고리즘 풀이/동적계획법 2017. 2. 17. 16:00
이번 글은 백준 알고리즘 문제 3745번 "오름세"를 다뤄본다.문제의 접근은 LIS(최장 증가 부분 수열) 알고리즘 문제이다.LIS O(nlogn) - http://mygumi.tistory.com/303 본인은 LIS 알고리즘을 다룬 글이 있다. (관련 글)관련 글은 시간 복잡도 O(n^2)으로 문제를 해결했다. 오름세 문제는 O(n^2)으로는 문제를 해결할 수 없다.시간초과를 초래하니 LIS의 또 다른 접근 방식으로 문제를 해결한다. 이번에 다룰 LIS의 시간복잡도는 O(nlogn)을 가진다.이분 탐색 또는 이진 탐색이라고 불리는 알고리즘을 이용하는 방식이다. (관련 글) 전체적인 의사코드로 표현하면 아래와 같다. // nums - 주어진 수열for each num in nums if(list.siz..