전깃줄
-
LIS 최장증가수열 알고리즘 -2- :: 마이구미알고리즘 2018. 3. 18. 14:52
이전에 LIS 알고리즘을 다룬적이 있다.다뤘던 글의 시간복잡도는 O(n^2) 이라면, 이번에는 O(nlogn) 을 다룬다.또한, 응용된 LIS 추적도 살펴본다.결론적으로 가장 긴 증가하는 부분 수열 시리즈(1 ~ 5) 등과 같은 문제들을 해결할 수 있다.이 방식은 이분 탐색을 요구한다.LIS O(n^2) - http://mygumi.tistory.com/69이분 탐색 - http://mygumi.tistory.com/72참고 링크 - http://www.crocus.co.kr/681 O(nlogn) 방식의 경우에는 이분 탐색을 활용한 방식이다.구현에 대한 흐름은 다음과 같다. 배열 마지막 요소보다 새로운 수가 크다면, 배열에 넣는다.그렇지 않다면, 그 수가 들어갈 자리에 넣는다. (이분 탐색을 통해 들어..