LIS(Longest Increasing Subsequence - 최장 증가 수열) 알고리즘 (1)

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

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

---

!본 글에서는 최장 증가 수열의 길이만 구한다!

또한 본글에서 설명하는 알고리즘의 시간복잡도는 O(N^2)이므로 매우 느리다.

크기가 작은 배열에서 간단한 아이디어로 구현을 하고싶을 때 사용하기 바람.

 

1. LIS의 길이와 수열을 O(N^2)으로 구하는 방법 : 여기(링크)

2. LIS의 길이를 O(N*log(N))으로 구하는 방법 : 여기(링크)

3. LIS의 길이와 수열을 O(N*log(N))으로 구하는 방법 : 여기(링크)

 

LIS는 어떤 수열의 증가하는 부분 수열중 가장 긴 부분 수열을 찾는 알고리즘이다.

예를 들어 {10, 20, 10, 30, 20, 50}이라는 수열이 있을 때 가장 긴 증가하는 부분수열은 {10, 20, 30, 50}이 될 것이다. 

위 예제의 경우 길이가 짧아서 눈대중으로 금방 찾을 수 있고 간단한 아이디어로도 금방 해결할 수 있지만, 수열의 길이가 길어질 경우는 골치가 아파진다.

LIS는 이런 경우에서 쓸 수 있는 알고리즘이다.

 

설명

---

LIS는 기본적으로 Dynamic Programming(DP)를 이용한다. 

수열의 처음부터 시작하며 DP[index]에는 현재 index번째 값을 포함하여 가장 긴 증가수열의 길이를 저장한다.

때문에 DP[index]값에는 수열의 처음부터 index-1까지 작은 수의 DP값중 가장 큰 값+1을 저장하면 된다.

만약 작은 수가 없었다면 1을 저장한다.

얻은 DP값중 가장 큰 값이 이 알고리즘이 요구하는 답(가장 긴 증가수열의 길이)이다.

 

위에서 언급한 {10, 20, 10, 30, 20, 50}로 설명을 해보겠다.

 

 

1. {10, 20, 10, 30, 20, 50}

arr[0]이전에 arr[0]보다 작은 수는 없으므로 DP[0]에 1을 저장한다.

index	0	1	2	3	4	5
DP	1	0	0	0	0	0

2. {10, 20, 10, 30, 20, 50}

arr[1]이전에 arr[1]보다 작은 수의 DP값중 가장 큰 값은 1이므로 +1을한 2를 저장한다.

index	0	1	2	3	4	5
DP	1	2	0	0	0	0

3. {10, 20, 10, 30, 20, 50}

index	0	1	2	3	4	5
DP	1	2	1	0	0	0

4. {10, 20, 10, 30, 20, 50}

arr[3]이전에 arr[3]보다 작은 수의 DP값중 가장 큰 값은 2이므로 +1을한 3을 저장한다.

index	0	1	2	3	4	5
DP	1	2	1	3	0	0

위 과정들을 index가 5일때까지 마치면 저장된 DP는 다음과 같다.

index	0	1	2	3	4	5
DP	1	2	1	3	2	4

 

구한 DP값중 가장 큰 값은 4이므로 가장 긴 증가하는 부분수열의 길이는 4이다. 

 

구현

---

항상 하는 말이지만 DP는 아이디어를 뽑아내기가 어렵지 구현은 점화식만 쓰면 되기 때문에 쉽다.

int num[] // 숫자 배열
int dp[] //dp
int ans=0; // 답
for (int i = 0;i < n;i++) {
	int tmp = 0;
	for (int j = 1;j < i;j++) {
		if (num[j] < num[i]) {
			tmp = max(tmp, dp[j]);
		}
	}
	dp[i]=tmp;
    ans = max(dp[i],ans);
}

이로써 최장 증가 수열의 길이를 구해보았다. 이 코드를 그대로 쓰면 백준 11053번 (가장 긴 증가하는 부분 수열)을 해결할 수 있다!

 

그러나 이 알고리즘은 느리다.

index를 늘려가며 이중 for문을 돌기 때문에 O(N^2)의 시간이 걸린다고 할 수 있다. 

이는 num[]배열을 돌며(O(N)) 최적의(자기보다 작은데 dp값은 최대인)곳을 찾기 위해 num[]배열을 다시 돌기(O(N)) 때문인데, 최적의 위치를 찾는 것을 O(logN)으로 줄여 O(N*logN)으로 줄인 알고리즘의 설명은 여기(링크)에 있다. 반드시 본 글을 정확히 이해한 후 넘어가길 바란다.