LIS(Long Increasing Subsequence ) 알고리즘

스터디 숙제는 아니지만 공부하다 보니 DP 대표적인 알고리즘인 LIS에 대해 공부하게 되었다.

1. Long Increasing Subsequence 란 ?

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.
이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

오름차순으로 정렬되어야하므로 원소들 사이의 대소관계 즉, 이전 원소보다는 그 뒤에 오는 원소가 더 커야한다는 조건이 존재한다.

 

예를 들어 10 20 10 30 20 50 이라고 하자. 

이때 만들 수 있는 증가하는 부분 수열은 {10, 20, 30 ,50} , {20 ,50} , {10,30,50} 등 여러가지이다. 

이중 가장 긴 {10, 20, 30 ,50} 부분수열을 찾는 게 목적이다. 

 

• DP로 풀 수 있는 유명한 알고리즘으로 시간 복잡도가 O($n^{2}$)인 풀이와 시간복잡도가 nlogn 인 풀이가 있다.

2. DP를 활용한 시간 복잡도가 O($n^{2}$)인 풀이

• dp 라는 배열에 arr[i] 값을 마지막으로 가지는 가장 긴 부분 수열의 길이를 저장해둔다. 
• arr배열에서 자신의 이전 인덱스에 대해 탐색하며 자신보다 작은 값 중 가장 큰 값을 찾는다. 
  가장 큰 값을 가지는 인덱스의 dp 값 + 1 로 dp 값을 저장해준다. 
• 매번 이전을 탐색해야되므로 시간 복잡도가 O($n^{2}$) 이다.

편의상 dp[0] = 0으로 둔다. 

2. CODE 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int arr[1001] = { 0 };
int dp[1001] = { 0 };

int main() {
	int n;
	scanf("%d", &n);
	//arr배열
	for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
	//기준이 되는 인덱스 지정
	for (int i = 1; i <= n; i++) {
	//이전 인덱스 탐색
		for (int j = 0; j < i; j++) {
			//arr값이 자신보다 작은 값 중 최대인 dp값 +1 사용 
			if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	printf("%d", *max_element(dp, dp + (n + 1)));
}

DP값을 출력해보면 표와 동일하게 나오는 것을 확인할 수 있다. 

3. DP를 활용한 시간 복잡도가 O(n log n)인 풀이

가장 긴 증가하는 부분수열2 (www.acmicpc.net/problem/12015) 같은 경우 조건이 1000000으로 시간 복잡도가 $n^{2}$ 인 위의 풀이로는 시간 초과가 난다. 

그렇다면 어떻게 시간을 줄일 수 있을까?

자신의 인덱스 이전부분에서 자신의 arr 보다는 작으면서 가장 큰 값을 찾는 탐색과정에서 이분탐색을 사용할 수 있다.

즉, dp[i]를 구하기 위해 a[i]값을 a[0] ~ a[i-1]값과 모두 비교해볼 필요가 없다는 것이다.

 

새로운 배열 lis를 만들어보자. lis의 길이가 곧 가장 긴 부분 수열의 길이다. 

* 이때 주의할 점은 lis배열의 값이 가장 긴 부분 수열의 구성원소가 아니라는 점이다. 

 

•  lis의 맨 마지막 원소보다 현재 i번째 원소가 더 큰 경우

  -> lis의 가장 마지막 값 + 1을 넣어준다. lis[i] = lis[i-1] + 1
  
  

•  lis의 맨 마지막 원소보다 현재 i번째 원소가 더 작거나 같은 경우

  현재 i번쨰 원소가 들어갈 수 있는 위치를 이분탐색으로 찾아줍니다.

  i번째 원소가 들어갈 수 있는 위치란 ? i번째 원소 값 이상이 처음으로 나오는 위치를 얘기한다. 다른 말로 하면 lower bound이다. 

  start = 1, end = 자신의 인덱스로 두고 이전값들에 대하여 자신보다 큰 값이 처음으로 나오는 인덱스를 구합니다.

* 주어진 그림에서는 인덱스가 1부터 시작하므로 부분 수열의 길이는 lis.size() -1 인 4가 된다. 

3. CODE

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int arr[1000001] = { 0 };
vector<int>lis;

void binary_search(int size, int i) {
	int idx, start = 1, end = size;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (lis[mid] >= arr[i]) {
			idx = mid;
			end = mid - 1;
		}
		else start = mid + 1;
	}
	lis[idx] = arr[i];
}

int main() {
	int n;
	scanf("%d", &n);
	//arr배열
	for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
	lis.push_back(0);
	for (int i = 1; i <= n; i++) {
		//lis의 back보다 크므로 arr값을 lis에 넣어줌
		if (arr[i] > lis.back()) lis.push_back(arr[i]);
		else  //lis의 back보다 작거나 같은 경우 이진탐색으로 lower bound를 찾아주자.
			binary_search(lis.size(), i);
	}
	printf("%d", lis.size() - 1);
}