LIS 알고리즘 (2)

앞에 LIS알고리즘은 O(n*n)의 시간복잡도를 가진다.
여기서 포스팅할 알고리즘은 lower bound를 이용한 O(nlog(n)) 알고리즘이다.

Lower Bound와 Upper Bound는 헤더파일 <algorithm>에 구현되어 있다.std::lower_bound( [배열의 처음 값의 주소], [배열의 끝 값의 주소], 찾고자 하는 값(k), [정렬])std::upper_bound( [배열의 처음 값의 주소], [배열의 끝 값의 주소], 찾고자 하는 값(k), [정렬])
[정렬] 에 아무것도 입력하지 않았을 경우 배열이 오름차순으로 정렬되어 있다고 가정하고 연산을 진행한다.반환 값으로 bound에 해당하는 주소값이 반환되므로,  함숫값에서 배열의 처음 값의 주소를 빼 줘야 몇 번째 인덱스인지 알 수 있다.

[출처] 알고리즘 기초 - Lower Bound & Upper Bound|작성자 bestmaker

저번 알고리즘과는 달리 dp배열(cache 배열)에  index가 아닌 숫자 그자체를 집어넣는다.

코드를 먼저 보고 예제를 넣어 설명을 하도록하겠다.

#include <cstdio> #include <algorithm> using namespace std; int arr[1001],dp[1001]; int main(){     int N, size = 1;     int lower;     scanf("%d", &N);     for (int n = 1; n <= N; n++)         scanf("%d", &arr[n]);     dp[1] = arr[1];     for (int n = 2; n <= N; n++){         if (dp[size] < arr[n]){             size++;             dp[size] = arr[n];         }         else{             lower = lower_bound(dp + 1, dp + size + 1, arr[n]) - dp;             dp[lower] = arr[n];         }         for (int s = 1; s <= size; s++)             printf("%d,", dp[s]);         printf("\n");     }     printf("%d\n", size);     return 0; } 만약 입력을 5개의 수 {1, 5, 3, 2, 4}를 넣어 본다고 가정해보자. n == 1 : dp[1]에는 먼저 배열의 처음값인 1이 들어갈 것이다. dp배열 : {1} n == 2 : dp[2]에는 dp[1] < 5 이기 때문에 5가 들어간다. dp배열 : {1,5} n == 3 : dp[3]에는 dp[2] > 3 이므로 lower bound를이용하여 dp내부에 3이 있는지 확인한다. 없지만 1보다 크기때문에 index == 2이므로 3이 들어간다. dp배열 : {1,3} n == 4 : 마찬가지 방법으로 2가 index == 2에 들어간다. dp배열 : {1,2} n == 5 : dp[4] < arr[5] 이므로 size가 증가하고 4가 들어간다. dp배열 : {1,2,4} <dp 배열에 들어가는 숫자는 LIS와 무관하다.> 단지 dp 배열의 크기가 LIS인것 이다. Colored by  해당 LIS는 {1, 3, 4}뿐이지만 최종 dp배열에는 {1, 2, 4}가 들어간다. Color Scripter

cs