Longest Increasing Sub-sequence Algorithm(LIS, 최장 증가 부분 수열 알고리즘)

 

Longest Increasing Sub-sequence Algorithm(LIS)

동적계획법(DP)문제를 풀다가 우연찮게 해당 알고리즘의 문제를 풀게되면서 이전 기억을 살려 다시한번 정리를 해보려고 한다.

 

해당 문제는 최장길이만 구하다 보니 동적계획법을 이용해서 해결이 되었지만, 더 다양한 문제를 해결하기 위해 그리고 LIS알고리즘을 더 잘 이해하기 위해 해당 페이지에 정리를 하려고 합니다.

정의(Definition)

주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘

1. 부분 수열은 연속적이거나 유일한 필요가 없다.
2. 최장길이를 구하거나, 해당 부분수열을 구할 수 있다.
3. 여러 시간복잡도로 문제를 해결할 수 있다.

부분수열이란?

주어진 수열에서 특정 원소들을 선택해서 만들어진 수열을 그 수의 부분 수열

증가하는 부분 수열

LIS 알고리즘에서 말하는 증가하는 부분 수열은 위 그림에서도 보다시피 선택된 부분수열이 오름차순을 유지할때 해당 부분수열을 증가하는 부분수열이라고 한다.

---

해당 문제를 해결하는 방법은 다양한다. 어떠한 방법으로 해결하느냐에 따라 시간복잡도 또한 다르다.

1. DP의 사용
2. 이분탐색의 사용(Lower-bound의 사용)
3. 해당 구성 부분수열까지 구하는 방법

동적계획법의 사용(with Dynamic Programing)

먼저 가장 쉽게 문제를 해결할수 있는 방법인 동적계획법을 이용해서 문제를 해결해보려고 한다.

다만, 해당 문제의 경우 최장길이만 구할 수 있기 때문에 길이를 구하는데 적합한 문제라고 생각한다.

1. 동적계획법을 사용하는 만큼 dp배열을 선언
2. 해당수열을 전부 탐색
3. dp에 저장된 배열중 가장큰 값을 출력

dp테이블에 저장하는 값은 0~해당 인덱스까지의 가장긴 부분 수열의 길이를 저장하는 테이블이다.

 

즉, db[i]의 테이블은 nums[i]>nums[0~i-1], dp[i]에 저장된 길이와 앞의 조건을 만족하는 인덱스에 해당하는 dp의 값 + 1 중 큰 값을 저장하면 된다.

해당 그림에서 보는 것처럼 인덱스 2까지는 증가부분수열을 만족하지 않아 dp에 저장된 값이 1임을 알수 있다.

 

하지만 index=3의 경우를 보면 nums[3]은 nums[1], nums[2]의 값보다 크다. 따라서 그경우 dp[3]의 값이 dp[1]+1, dp[2]+1보다 큰 값을 저장해주면 된다.

 

이러한 과정을 끝까지 진행하게 되면 dp에는 다음과 같이 값이 저장된다.

이렇게 저장된 dp의 값중 가장큰 값을 구하면 해당 값이 해당 수열의 가장 긴 증가부분수열의 길이가 된다.

소스코드

int lis_dp(int n){
	int max_length = 0;

	for (int i = 0;i < n;i++) {
		dp[i] = 1;
		for (int j = 0; j < i;j++) {
			dp[i] = (nums[j] < nums[i]) && (dp[j] >= dp[i]) ? dp[j] + 1 : dp[i];
		}
		max_length = (max_length < dp[i]) ? dp[i] : max_length;
	}
	return max_length;
}

해당 소스코드에서 알수 있는 것과 같이 반복문을 두번 수행하기 때문에 긴 시간복잡도를 갖는다

시간복잡도

해당 알고리즘의 풀이는 2중 for문으로 해결되기 때문에 다음의 시간복잡도를 갖는다.

$$O(N^2)$$

이분탐색의 사용(with Binary Search)

dp를 사용하면 간단하게 문제를 해결할 수 있지만 위에서 보다시피 시간복잡도가 O(N^2)를 차지하고 있다.

즉 N의 값이 커지면 너무 오랜 시간을 갖게 되는 문제가 있는 것이다.

 

이런 시간문제를 해결하기 위해 나온 방법이 이분탐색을 활용하는 방법이다.

해당문제는 정렬되어있지 않는 수열인데 어떻게 이분탐색을 사용하는 것일까?

 

최장길이라는 점 그리고 증가부분수열이라는 점을 이용해서 이분탐색을 이용하는 것이다.

해당 nums의 원소가 들어가는 위치를 이분탐색을 사용해서 만들어 주는 것이다.

물론 이렇게 만들어진 배열이 부분수열의 요소는 아니다. 하지만 만들어진 lis테이블의 길이가 해당 LIS의 최장길이가 될것이다.

 

해당 이분탐색을 사용하는것에 있어서 STL함수를 이용할수 있는데 lower_bound() 함수를 사용하는것이다.

target의 값보다 같거나 큰 숫자가 배열 몇번쨰에 처음등장하는지 찾는 함수로 이분탐색을 따로 만들 필요가 없다.

소스코드

int lis_bs(int n, int* nums) {
    int lis[1001];
    int max_length = 0;

    for (int i = 0; i < n; ++i) {
        auto pos = lower_bound(lis + 1, lis + max_length + 1, nums[i]);
        *pos = nums[i];
        if (pos == lis + max_length + 1)
            max_length++;
    }

    return max_length;
}

시간복잡도

소스코드에서 보면 알다시피 내부 반복문에서 진행이 for문을 통해 탐색을 이루어지는 것이 아닌 이분탐색으로 이루어진다.

즉, 최종시간 복잡도는 다음과 같다.

$$O(N \log N)$$

최장증가 부분수열 구하기

지금까지 알아본 방법들은 전부 길이를 구하는 방법이다.

하지만, 최장증가 부분수열 자체를 구하고 싶은 경우도 있다 이런 경우 어떻게 문제를 해결할 수 있을까?

 

위의 이분탐색의 방법을 이용해서 해결을 해보겠다.

이분탐색의 방법을 보면 각 target의 위치를 찾아 해당 위치에 갑을 넣어주는데 그때의 타겟이 위치할 인덱스를 따로 관리해주면 문제를 해결이 가능하다.

위 그림을 보면 각 요소가 lis테이블에 위치할때의 인덱스를 pos 테이블에서 관리를 하게 된다.

그리고 pos의 값이 1, 2, 3의 요소를 순서대로 꺼내서 출력하면 된다.

 

위에서 보면 pos[3], pos[4], pos[6] 이렇게 출력하면 된다.

소스 코드

int lis_pos[1001];
int nums[1001];

void backTrace(int idx, int order) {
    if (idx == -1) {
        return;
    }

    if (lis_pos[idx] == order) {
        backTrace(idx - 1, order - 1);
        cout << nums[idx] << " ";
    }
    else {
        backTrace(idx - 1, order);
    }
}

int lis_bs(int n, int* nums) {
    int lis[1001];
    int max_length = 0;

    for (int i = 0; i < n; ++i) {
        auto pos = lower_bound(lis + 1, lis + max_length + 1, nums[i]);
        *pos = nums[i];
        lis_pos[i] = distance(lis, pos);
        if (pos == lis + max_length + 1)
            max_length++;
    }

    return max_length;
}

LIS를 수행하면서 lis_pos를 완성시킨다. 그리고 backTrace를 통해 출력하면된다.

다만, 해당경우는 back_trace가 아니라 반복문을 통해서도 구현할 수 있으니 수열을 만드는 작업은 선택적으로 구현하면 될 거 같다.

시간복잡도

해당 알고리즘 또한 결국 이분탐색을 이용해 lis를 구하는 과정에서 유추되는 관계로 시간복잡도는 이분탐색을 이용한 lis와 같은 시간복잡도를 갖게 된다.

$$O(N \log N)$$

---

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

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

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