[알고리즘] 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

가장 긴 증가하는 부분 수열이란

3 9 2 10 2 11 19

라는 수열이 있을 때 부분 수열은 3 9 2, 10 2 19, 9 2 10 등 많은 수열이 있지만 그 중에서도 3 9 10 11 19를 뽑으면 오름차순을 유지하면서 가장 긴 부분 수열을 뽑을 수 있다. LIS알고리즘이란 이 수열의 길이를 빠르게 찾아내는 방법을 말한다.

그렇다면 이 수열을 어떻게 구할 수 있을까?

1. 브루트포스 완전탐색

• 모든 수열을 다 구해보면 된다. 그렇다면 1 2 3 4 라는 수열이 있다면 각 자리의 수를 사용하거나 혹은 사용하지 않는 경우의 수를 샐 수 있으므로 시간 복잡도는 O(2^N) 으로 너무 긴 시간이 걸린다.

2. 동적계획법 (Dynamic Programming)

• 각 자릿수가 자신을 포함했을 때의 최장 길이 부분 수열의 길이를 저장하는 메모이제이션을 사용하면 속도를 줄일 수 있지 않을까?

idx 1 2 3 4 5

value

2

10

4

9

7

먼저 첫번째 DP는 자신만 있으므로 1일 것이다.

DP[1] = 1

2번을 확인한다. value[1] 은 value[2] 보다 작다. 그러므로 DP[2] = 2

3번을 확인한다. value[2] 은 value[3]보다 작지만, value[2]보다는 작다. 그러므로 DP[3] = 2

4번을 확인한다. value[3], value[1]은 value[4]보다 작고 value[2]는 더 크다. 그러므로 DP[3] = 3

.

.

아하.. 점화식이 보이는 것 같다.

if (value[i] > value[j]) DP[i] = DP[j] + 1

단, DP[i]가 갱신되고 나서 더 작은 값으로 갱신될 수 있으므로

if (value[i] > value[j]) DP[i] = max (DP[i], DP[j] + 1)

이것이 추가되야할 것이다. 그리고 i번째를 확인할 때 지금까지 지나온 모든 수를 확인해볼 필요가 있으므로

for(int i = 2; i < N; i++){ // DP[1] 은 이미 1이므로
		for(int j = 1; j < i; j++){
			if (value[i] > value[j]) DP[i] = max (DP[i], DP[j] + 1)
		}
}

이렇게하면 점화식을 완성하게 되고 O(2^N) 에서 O(N^2) 으로 대폭 줄일 수 있다!

3. 동적계획법 + 이분탐색

O(N^2)은 완전탐색에 비하면 훌륭하지만 N이 조금만 커져도 사용할 수 없는 시간이다.

다시한 번 위 점화식을 살펴보자

for(int i = 2; i < N; i++){ // DP[1] 은 이미 1이므로
		for(int j = 1; j < i; j++){
			if (value[i] > value[j]) DP[i] = max (DP[i], DP[j] + 1)
		}
}

흠.. 내부 for문을 없앨 수 없을까?

내부 for문을 도는 이유가 뭘까? 지금 i 번째의 수를 포함 했을 때 길이를 알고자하는 것이다.

아하.. 그렇다면 현재 수열에서 i번 value가 어디에 들어가면 최장수열이 되는지를 알아보면 되지 않을까?

그리고 정렬되어 있는 수열에서 위치를 찾을 수 있는 탐색법은 바로 이분탐색이다..!

idx 1 2 3 4 5

value

2

10

4

9

7

이 예제를 다시 써보자

1. 처음 수열에는 2만 있다. 수열 :: 2
2. 10은 2보다 크므로 뒤에 넣는다. 수열 :: 2 10
3. 4를 포함하여 증가하는 부분 수열을 만들기 위해서는 현재 4가 가장 커야한다! 그러므로 10을 지우고 2가 들어온다. 수열 :: 2 4
4. 9는 4보다 크므로 그냥 들어온다. 수열 :: 2 4 9
5. 7은 3번처럼 2 4 7이 되어야 본인 포함 최장 증가 수열이다.

여기서 가장 중요한 점은 그렇다고 이 수열이 가장 긴 증가하는 부분 수열 자체가 되는 것은 아니고 길이만 나타낸다는 것이다.

어떻게 이것이 가능할까? 이유는 총 유지되는 수를 왜곡하지 않는다는 것이다. 위 3번에서 4를 2 4 10으로 넣지 않고 가장 큰 숫자로 가정하고 넣어버렸다. 하지만 자기보다 큰 숫자가 오면 수열에 포함하면서 DP에서 포함하던 최장길이의 성질은 그대로 가지게 된다.

그리고 저 새로들어오는 value들이 어디로 가야할지 정해주는 것이 이분탐색이 할 일이다.

여기서는 upper_bound를 해줘야한다. 만약 2 3 7 9 수열에서 4가 들어오면 4의 위치는 7을 대신해 2 3 4 9 가 되어야한다. 2, 3을 대신하면 안되므로 가장 자신과 가까운 큰 값을 찾도록 이분탐색 해야한다.

난 lo + 1 < hi 조건으로 이분탐색하는 것을 좋아한다. lo와 hi 사이에 항상 mid가 존재함이 보장되기 때문이다.

for(int i = 1; i < N; i++){
         int value = connect[i];
 
         if(answer[answer.size() - 1] < value) {
             answer.push_back(value);
             continue;
         }
 
         int hi = answer.size();
         int lo = -1;
 
         while(lo + 1 < hi){
             int mid = (hi + lo) / 2;
     
             if(answer[mid] < value){
                 lo = mid;
             }else{
                 hi = mid;
             }
         }
 
         answer[hi] = value;
     }