O(nlogn)의 시간복잡도 - 길이만 구하기
기존 LIS알고리즘은 배열의 원소를 하나씩 탐색하면서, 그 이전의 원소들을 모두 탐색하기 때문에 O(n^2)의 시간복잡도를 갖는다.
더 빠른 풀이를 위해 O(nlogn)의 시간복잡도를 갖는 알고리즘을 이용할 수 있는데, 이 알고리즘을 위해서는lower_bound를 이용해야 한다.
즉, 원래의 O(n^2) 알고리즘에서 이전의 원소들을 탐색하는 과정(O(n)) 을 lower_bound(O(logn))을 이용하여 시간을 줄여주는 것이다.핵심 아이디어는, LIS를 만들기 위해서는 만드는 과정에서LIS의 마지막 원소가 가능한 작을수록 더 긴 LIS를 생성할 수 있다는 것이다.그러므로 원소가 들어올 때, 만약 현재 생성된 LIS의 마지막 원소보다 작은 경우, LIS에 들어갈 위치를 찾은 후(O(logn)) 원소를 대체한다.
- 간단한 예시로,[1, 2, 3, 7, 5, 6] 수열이 있을 때,
이러한 원리로 차례대로 원소가 들어올 때, 다음과 같은 과정을 거친다.
-
[1]
-
[1, 2] (2 > 1)
-
[1, 2, 3] (3 > 2)
-
[1, 2, 3, 7] (7 > 3)
-
[1, 2, 3, 5] (5 < 7. 5가 들어갈 자리를 찾은 후 7이 5로 대체 됨)
-
[1, 2, 3, 5, 6] (6 > 5)
- [10, 20, 10, 30, 20, 50] 배열을 예로 들면
-
K = [10]
-
K = [10, 20]
-
K = [10, 20] (10이 첫번째 자리로 들어감)
-
K = [10, 20, 30]
-
K = [10, 20, 30] (20이 두번째 자리로 들어감)
-
K = [10, 20, 30, 50]따라서 LIS는 [10, 20, 30, 50] 이 만들어지고 길이는 4로 나오게 된다.
- [10, 20, 10, 30, 25, 50] 배열을 예로 들면
-
K = [10]
-
K = [10, 20]
-
K = [10, 20] (10이 첫번째 자리로 들어감)
-
K = [10, 20, 30]
-
K = [10, 20, 25] (25가 세번째 자리로 들어감)
-
K = [10, 20, 25, 50] 으로 나오게 된다.
이처럼 위의 알고리즘을 이용하면 K배열에 항상 LIS가 만들어지는 것 같지만 실제로는 이 알고리즘을 이용하면 길이만 구할 수 있게 된다.
[3, 5, 2, 6, 1] 배열은 다음과 같이 진행이 된다.
-
K = [3]
-
K = [3, 5]
-
K = [2, 5]
-
K = [2, 5, 6]
-
K = [1, 5, 6]
실제로 LIS는[3, 5, 6]이지만 K에는 [3, 5, 2, 6, 1]로는 만들어 질 수 없는 부분수열인 [1, 5, 6]이 들어가게 된다.
O(nlogn)의 시간복잡도 - 길이와 수열 모두 구하기
위의 알고리즘에서 주어진 수열의 각각의 원소들이 K 배열에 들어가는 index를 배열로 별도로 저장한다.그리고 나서 마지막원소부터 LIS의 길이를 감소시켜 가면서, 처음으로 해당 길이의 index가 나오는 원소만 뽑아낸다.
[3, 5, 2, 6, 1] 배열을 예로 들면,
-
K = [3]
-
K = [3, 5]
-
K = [2, 5]
-
K = [2, 5, 6]
-
K = [1, 5, 6]
이므로 3은 1번째, 5는 2번째, 2는 1번째, 6은 3번째, 1은 1번째 index에 들어가게 된다.즉, index 배열은[1, 2, 1, 3, 1]이 되는 것이다. LIS의 길이는 현재 3이므로 index 배열의 뒤에서부터 처음으로 3이 나오는 원소는6이며,그 다음 처음으로 2가 나오는 원소는5, 그 다음 처음으로 1이 나오는 원소는3이 된다.따라서 이를 역으로 정렬하면[3, 5, 6] 으로 우리가 구하고자 하는 LIS가 나오게 된다.
