[알고리즘] 최장 증가 부분 수열 (LIS)

최장 증가 부분 수열 Longest Increasing Subsequence (LIS)

---

- 배열의 수열에서 연속적으로 값이 증가하는 요소를 연결할 때, 길이가 가장 긴 수열을 찾음.

 

아래와 같은 배열이 있음.

0	1	2	3	4	5
10	20	10	30	20	50

 

증가 부분 수열을 찾으면 

10 - 20 - 30 - 50

10 - 30 - 50

10 - 20 - 50

10 - 50

20 - 30 - 50

20 - 50

30 - 50

임. 최장 증가 부분 수열은 10 - 20 - 30 - 50로, 길이가 4임.

 

LIS를 구하는 방법 1. DP 2. 이진탐색 3.  Segment Tree

 

Dynamic Programming < O(n^2) >

---

 

DP를 이용하면, 최장 길이는 현재 나온 값보다 작은 이전에 나온 값 중 최장 길이에 + 1을 하면 됨.

 

배열 arr[i]

0	1	2	3	4	5
10	20	10	30	20	50
1	2	1	3	2	4

 

- arr[0]은 항상 길이가 1이 나옴.

 

- arr[1]은 arr[0]보다 값이 크므로 2가 됨.

 

- arr[2]는 arr[1]보다 값이 작음. arr[2]는 arr[0]보다 값이 작음. 따라서, 1로 시작됨.

 

- arr[3]은 3가지 경우가 있음.

 1. arr[3] > arr[2] : 2가 됨.

 2. arr[3] > arr[1] : 3이 됨.

 3. arr[3] > arr[0] : 2가 됨.

이를 위해 이전 인덱스의 값을 확인해야 해서 시간 복잡도는 O(n^2).

 

- arr[4]는 arr[3]보다 값이 작음. arr[4]는 arr[0], arr[2]보다 값이 크므로 2가 됨.

 

- arr[5]는 이전 요소에서 길이가 가장 긴 arr[3]에 1을 더해 4가 됨.

 

Top-down

static int LIS(int n) {
    // 탐색하지 않던 위치의 경우 1로 초기화
    // arr[2]의 경우
    if (dp[n] == 0) {
        dp[n] = 1;

        // n 이전의 노드들을 탐색
        for (int i = n - 1; i >= 0; i--) {
            // 이전의 노드 중 arr[n]의 값보다 작은 걸 발견했을 경우
            // 이전 노드 중 최대를 찾아 1을 더해줌
            // 1을 더하는 이유는 최대 길이가 증가하기 때문
            if (arr[i] < arr[n]) {
                dp[n] = Math.max(dp[n], LIS(i) + 1);
            }
        }
    }
    return dp[n];
}

 

n = 0일 때, dp[0] = 1;

 

n = 1일 때, i는 0.

arr[0] < arr[1]이므로 dp[1] = Math.max(dp[1], LTS(0) + 1);

dp[1] = 2; 

 

dp[2]는 null으므로 1.

 

이런식으로 LIS를 찾음.

Bottom-up

for(int i = 0; i < n; i++) {
    // 모든 원소를 1로 초기화
    dp[i] = 1;

    // 0 ~ i 이전 원소들 탐색
    for(int j = 0; j < i; j++) {

        // j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
        if(arr[j] < arr[i] && dp[i] < dp[j] + 1) {
            dp[i] = dp[j] + 1;  // j번째 원소의 +1 값이 i번째 dp가 된다.
        }
    }
}