[C code] DP를 이용한 LIS(Longest Increasing Subsequence; 최장 증가 수열)

최장 증가 부분 수열, LIS는

임의의 수열에서 몇 개의 수를 제거하여 만든 부분수열 중

오름차순으로 정렬된 가장 긴 수열을 말한다

---

예를 들어 다음 수열이 주어졌다고 하자.

10 20 10 30 20 50

위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.

10 10 30 20 (20, 20 제거)

10 30 20 50 (20, 10 제거)

20 10 30 (10, 20, 50 제거)

10 20 50 (10, 30, 20 제거)

...

이들 중 네번째 수열은 오름차순으로 정렬되어 있다. 이를 '증가 부분 수열'이라고 한다.

그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다.
부분수열 10 20 30 50은 LIS이다.

한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열

5 1 6 2 7 3 8

에서 부분수열

1 2 3 8
5 6 7 8

은 모두 길이가 4인 LIS인 것이다

 

- 나무위키

---

DP를 이용한 알고리즘은 다음과 같다

 

int *arr;

void LIS(int n)
{
    int dp[n+1];
    
    for(int i=0 ; i<n ; i++)
    {
        dp[i] = 1;
        for(int j=0 ; j<i ; j++)
        {
            if(arr[i] > arr[j])
            {
                if (dp[i] < dp[j] + 1) // max(dp[i], dp[j]+1)
                {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
}

 

위 코드와 같이 이중 반복문을 이용하여

dp 배열을 채우기 때문에 O(N²)의 시간복잡도를 가지게 될 것이다

---

dp[i]를 채우기 위하여 arr[0] ~ arr[i-1]를 다 훑어봐야 하는가? 그건 아니다

이분 탐색, 위상 정렬을 이용한 O(NlogN)의 시간복잡도를 가지는 알고리즘도 있다