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

최장 증가 부분 수열(LIS)

Longest Increasing Subsequence 를 줄여서 LIS라고도 불리는 이 알고리즘은 수열에서 연속적으로 값이 증가하는 요소들을 연결시켰을 때, 그 길이가 가장 길어지는 수열의 길이를 찾는 방법이다.

예를 들어, 아래 A라는 배열에 다음과 같이 값들이 들어 있다고 하자.

index	0	1	2	3	4	5	6
A[index]	5	2	3	8	1	4	7

이 경우에서 우리가 얻을 수 있는 증가 부분 수열은

1. 5 > 8
2. 2 > 3 > 8
3. 2 > 3 > 4 > 7
4. 3 > 8
5. 3 > 4 > 7
6. 1 > 4 > 7
7. 4 > 7

이고, 이 중 길이가 가장 긴 증가 부분 수열은 3번에 있는 길이 4짜리 수열이다.

 

LIS를 구하는 전략은 1) Dynamic Programming, 2) Segment Tree, 3) Binary Search 세 가지로 나뉘는데, 아직 다 공부한 상태가 아니므로 공부할 때마다 하나씩 추가하도록 하겠다.

Dynamic Programming - O(n²)

DP로 LIS를 구하는 것을 생각해보면, 어떤 특정한 지점의 최장 길이는 해당 지점 이전에 나왔던 수들 중, 값이 작은 수들이 가진 최장 길이에 1을 더하면 구할 수 있다. DP의 특징을 살려서 첫 인덱스부터 순차적으로 최장 길이를 구해가면 수열의 크기가 커져도 쉽게 구할 수 있을 것이다. 따라서, DP를 수행하는 배열 dp의 dp[x]는 x 지점에서의 최장 수열 길이가 될 것이다.

위에서 사용했던 배열 A를 예시로 살펴보자.

index	0	1	2	3	4	5	6
A[index]	5	2	3	8	1	4	7

1. A의 제일 처음 인덱스인 A[0]는 증가 부분 수열 길이가 항상 1이다. 자기 이전에 수열이 존재하지 않기 때문이다. 따라서 dp[0]에는 1이 들어간다.
2. A[1]의 LIS는 A[1] 의 값이 A[0] 보다 클 경우에는 2, 작을 경우에는 새로운 증가 부분 수열의 시작이므로 1이 될 것이다.
3. A[2]의 LIS는 다음과 같은 경우의 수를 고려해서 구할 수 있다.
   • A[2] > A[0], A[2] < A[1] :
     가장 긴 부분 수열을 만들어주면 되기 때문에 A[0]랑 연결시켜서 길이를 2로 만들어준다.
   • A[2] > A[1], A[2] < A[0] :
     가장 긴 부분 수열을 만들어주면 되기 때문에 A[1]랑 연결시켜서 길이를 2로 만들어준다.
   • A[2] > A[1], A[2] > A[0] :
     A[0]와 A[1] 중 길이가 더 긴 값과 연결해준다.
   • A[2] < A[0], A[2] < A[1] :
     증가 부분 수열을 만들 수 없기 때문에 그냥 지나간다.

위 세 단계를 반복적으로 수행하려면 결국 하나의 인덱스 당, 해당 인덱스 이전에 나왔던 모든 인덱스들의 값이 가진 LIS를 확인해야하는 작업이 필요하다. 따라서 이 방식은 O(n²) 의 복잡도를 가지게 된다.

 

위 내용을 일반화해서 코드로 만들어보자

 for (int i = 0 ; i < A.size() ; i++){
        if (dp[i] == 0) dp[i] = 1; // 일단 처음 만나는 위치는 무조건 1로 만들어 주기
        for (int j = 0 ; j < i ; j++){
            if(A[i] > A[j] && dp[j]+1 > dp[i]){ // 기준이 되는 인덱스 이전까지 모두 돌면서 기준이 되는 값고 크면서 LIS가 가장 큰 값을 찾는다.
                dp[i] = dp[j]+1; // 존재하면 해당 LIS에 1을 더한 값을 현재 위치의 길이로 지정
            }
        }
    }

생각보다 단순한다.

if(A[i] > A[j] && dp[j]+1 > dp[i])

이 조건이 헷갈릴 수도 있는데, 제일 큰 LIS 값을 찾아서 마지막에 한번에 넣어주는게 아니라, dp[i]은 처음에 1로 시작하기 때문에 중간에 길이가 1 이상이 되는 길이들을 만나면 계속 dp[i] 를 새로운 값으로 업데이트 시키는 것이다.

 

dp[j]+1을 해주는 이유는 dp[i] 가 1 일 경우에 이어주기 위해서는 dp[j]가 더 큰 값을 가져야 하기 때문에 1을 늘려주어서 비교하는 것이다.