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

LIS는 어떠한 수열에서 증가하는 부분 수열중 길이가 가장 긴 수열를 뜻합니다. LIS를 찾는 알고리즘은 다이나믹 프로그래밍을 이용한 O(N^2) 알고리즘과 이보다는 좀 더 복잡한 O(N log N) 알고리즘이 있습니다. 

 

부분 수열이란 어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 의미합니다.

---

O(N^2)

O(N^2) 알고리즘은 비교적 간단하게 구현할 수 있습니다.

dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이

 

dp[i]를 구하는 법은 1 ~ (i - 1)까지의 원소들 중 i번째 원소보다 값이 작은 것들 중 dp의 값이 가장 큰 것에 1을 더하면 된다.

 

즉, j = 1 ~ (i - 1)을 순회할 때, a[i]보다 a[j]가 작다면, dp[i] = max(dp[i], dp[j] + 1)을 하면 된다.

 

하지만 이 알고리즘은 1, 2, 3, .... , n번 반복문을 돌면서 n * (n + 1) / 2만큼 반복하면서 O(N^2)의 시간 복잡도를 가진다.

 

N이 1,000,000이 되면 대부분의 문제에서 시간 내로 풀 수 없게된다.

 

#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))

int n;
int a[1001];
int dp[1001];

int main()
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = i - 1; j >= 1; j--)
		{
			if (a[i] > a[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(ans, dp[i]);
	}
	printf("%d", ans);
}

---

O(N log N)

이 알고리즘을 이해하기 위해서는 Lower Bound에 대해 이해해야 합니다.

 

O(N^2) 알고리즘은 i번째 원소까지의 LIS를 구하려면 (i - 1) ~ i까지 순회를 해야하므로 1 ~ N까지의 LIS를 모두 구하며 O(N^2) 의 시간이 소모됩니다. 하지만 O(N log N) 알고리즘은 O(N^2)과 비슷하게 순회하는 부분이 이진 탐색을 통해 O(log N) 시간에 수행을 하기에 전체 시간 복잡도가 O(N log N)이 됩니다.

 

이 알고리즘은 임의 리스트 L을 만들어 LIS의 길이를 구합니다.

L[i] = 길이가 i인 증가하는 부분 수열을 만들 수 있는 마지막 원소 중 가장 작은 값

따러서 L의 크기가 만들 수 있는 LIS의 길이가 됩니다.

 

리스트 L을 만드는 방법은 입력받은 수열의 원소들을 앞에서부터 순회하며, 아래의 과정을 통해서 만듭니다.

(순회하는 과정의 현재 원소를 T라고 하겠습니다.)

 

1. 리스트의 크기가 0이거나, 리스트의 마지막 원소가 T보다 작다면, 리스트에 T를 추가

 

2. 리스트의 마지막 원소가 T의 값보다 크다면 T의 lower_bound를 구해 해당 위치의 값을 T로 바꿉니다.

 

위 과정을 통해서 나온 리스트의 크기가 LIS의 길이가 됩니다. 밑에 예시를 통해서 다시 보겠습니다.

 

10

20

10

30

20

50

위와 같은 수열이 주어졌을 때 LIS의 길이를 구해보겠습니다. (

 

처음 상태

처음 리스트는 아무런 값이 없습니다.

 

i  = 0

리스트의 크기가 0이기에 리스트에 1번째(10) 값을 넣습니다.

10

i  = 1

리스트의 마지막 값보다 2번째(20)값이 크기에 리스트에 추가합니다.

10

20

i  = 2

리스트의 마지막 값보다 3번째(20)값이 작기 때문에 lower_bound인 0번째를 10으로 바꿉니다

10

20

i  = 3

리스트의 마지막 값보다 4번째(30)값이 크기에 리스트에 추가합니다.

10

20

30

i  = 4

리스트의 마지막 값보다 5번째(20)값이 작기 때문에 lower_bound인 1번째를 20으로 바꿉니다

10

20

30

i  = 5

리스트의 마지막 값보다 6번째(50)값이 크기에 리스트에 추가합니다.

10

20

30

50

 

 

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n;

int main()
{
	scanf("%d", &n);

	vector<int> dp;
	for (int i = 1; i <= n; i++)
	{
		int t;
		scanf("%d",&t);
		if (dp.size() == 0 || t > dp.back()) dp.push_back(t);
		else
		{
			vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), t);
			*it = t;
		}
	}

	printf("%lu", dp.size());

}