LIS(longest increasing sequence) - O(NlogN)

오늘은 DP의 특별한 문제 형태라고 할 수 있는 LIS를 알아보겠습니다.

보통의 DP로 풀게 되면 O(N^2)으로 풀게 됩니다. 하지만 N의 값이 커지면 O(NlogN)의 알고리즘이 필요합니다.

우선 LIS 문제 정의 부터 알아보겠습니다.

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.

[출처 : geeksforgeeks]

이것을 푸는 보통 DP 코드를 보겠습니다. 

/* Dynamic Programming C/C++ implementation of LIS problem */
#include <stdio.h> 
#include <stdlib.h> 
  
/* lis() returns the length of the longest increasing 
  subsequence in arr[] of size n */
int lis(int arr[], int n) 
{ 
    int *lis, i, j, max = 0; 
    lis = (int*)malloc(sizeof(int) * n); 
  
    /* Initialize LIS values for all indexes */
    for (i = 0; i < n; i++) 
        lis[i] = 1; 
  
    /* Compute optimized LIS values in bottom up manner */
    for (i = 1; i < n; i++) 
        for (j = 0; j < i; j++) 
            if (arr[i] > arr[j] && lis[i] < lis[j] + 1) 
                lis[i] = lis[j] + 1; 
  
    /* Pick maximum of all LIS values */
    for (i = 0; i < n; i++) 
        if (max < lis[i]) 
            max = lis[i]; 
  
    /* Free memory to avoid memory leak */
    free(lis); 
  
    return max; 
} 
  
/* Driver program to test above function */
int main() 
{ 
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printf("Length of lis is %d\n", lis(arr, n)); 
    return 0; 
} 

DP를 풀어보셨다면 이 코드를 금방 이해하실텐데요. 

이런식으로 풀면 O(N^2)이 됩니다. N이 대략 40000개 이상이 주어지면 1초 안으로 풀기가 어려워 집니다.

O(NlogN) 알고리즘의 쉽고 좋은 설명이 되어 있는 문서가 있습니다.

 

longest_increasing_subsequence.pdf

영어가 필요하진 하지만 해석이 전혀 어렵지 않기에 읽어보시면 정말 많은 도움이 되실거에요.

제 설명보다는 좋은 문서를 공유하는 것으로 마무리 하겠습니다. ^ㅡ^