-
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) 방식의 경우에는 이분 탐색을 활용한 방식이다.
구현에 대한 흐름은 다음과 같다.
- 배열 마지막 요소보다 새로운 수가 크다면, 배열에 넣는다.
- 그렇지 않다면, 그 수가 들어갈 자리에 넣는다. (이분 탐색을 통해 들어갈 자리를 찾는다)
말로도 간단하게 표현할 수 있듯이 코드도 간단하다.
dp[0] = array[0]; int idx = 0; for (int i = 1; i < n; i++) { if (dp[idx] < array[i]) { dp[++idx] = array[i]; } else { int ii = lower_bound(idx, array[i]); dp[ii] = array[i]; } } // ans => idx + 1
그림으로 표현하면 다음과 같다.
이것만으로 가장 긴 증가하는 부분 수열 문제 중 1 ~ 3 을 해결할 수 있다.
4 ~ 5번의 경우에는 LIS 길이뿐만 아니라, LIS 자체를 요구한다.
즉, 추적을 통해 LIS 를 구해야한다.
추적의 경우에는 본인은 너무 깊게 생각해서 헤맸다.
하지만 일반적으로 추적은 대부분 인덱스를 활용한다.
여기서도 인덱스와 함께 실제 값을 통해 구할 수 있다.
추적 배열을 추가한 흐름의 그림과 코드는 다음과 같다.
dp[0] = array[0]; tracking[0] = new Pair(0, array[0]); int idx = 0; for (int i = 1; i < n; i++) { if (dp[idx] < array[i]) { dp[++idx] = array[i]; tracking[i] = new Pair(idx, array[i]); } else { int ii = lower_bound(idx, array[i]); dp[ii] = array[i]; tracking[i] = new Pair(ii, array[i]); } }
추적이 필요한 LIS의 대표적인 문제의 링크는 다음과 같다.
전깃줄 -2 => https://www.acmicpc.net/problem/2568
가장 긴 증가하는 부분 수열 5 - https://www.acmicpc.net/problem/14003
다음은 "가장 긴 증가하는 부분 수열 5" 문제의 소스이다.
기타 소스들은 Github 을 참고하길바란다.
Github - https://github.com/hotehrud/acmicpc/tree/master/algorithm/lis
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566static int[] dp;private void solve() {int n = sc.nextInt();dp = new int[n];int[] array = new int[n];Pair[] tracking = new Pair[n];for (int i = 0; i < n; i++) {array[i] = sc.nextInt();}dp[0] = array[0];tracking[0] = new Pair(0, array[0]);int idx = 0;for (int i = 1; i < n; i++) {if (dp[idx] < array[i]) {dp[++idx] = array[i];tracking[i] = new Pair(idx, array[i]);} else {int ii = lower_bound(idx, array[i]);dp[ii] = array[i];tracking[i] = new Pair(ii, array[i]);}}Stack<Integer> stack = new Stack<Integer>();int temp = idx;for (int i = n - 1; i >= 0; i--) {if (temp == tracking[i].idx) {stack.push(tracking[i].value);--temp;}}System.out.println(stack.size());while(!stack.isEmpty()) {System.out.print(stack.pop() + " ");}}static int lower_bound(int end, int n) {int start = 0;while (start < end) {int mid = (start + end) / 2;if (dp[mid] >= n) {end = mid;} else {start = mid + 1;}}return end;}static class Pair {int idx;int value;Pair(int idx, int value) {this.idx = idx;this.value = value;}}cs 반응형'알고리즘' 카테고리의 다른 글
합병정렬 알고리즘 :: 마이구미 (0) 2018.04.14 퀵소트 알고리즘 :: 마이구미 (12) 2018.04.10 Line Sweep 알고리즘 :: 마이구미 (0) 2018.02.11 연쇄 행렬 곱셈 (Matrix chain multiplication) :: 마이구미 (1) 2017.11.27 디스조인트-셋(disjoint-set) :: 마이구미 (0) 2017.11.05