LIS(Longest Increasing Subsequence) 알고리즘

티스토리 뷰

알고리즘

LIS(Longest Increasing Subsequence) 알고리즘

jonyo 2020. 8. 25. 22:28

LIS(Longest Increasing Subsequence) 알고리즘은 '가장 긴 증가하는 부분 수열' 알고리즘으로도 불린다.

주로 그리디 알고리즘이나 다이나믹 프로그래밍의 예시로 등장한다.

LIS는 수열 내 증가하는 부분 수열 중 가장 긴 수열을 말한다.

예를들어 아래와 같은 수열이 존재할때

이때 가장 긴 증가하는 부분 수열은 {1,2,4}이며 길이는 3이다.

아래의 예시에서는 가장 긴 증가하는 부분 수열은 {10,20,30,50} 이며 길이는 4가 된다.

이제 이 알고리즘을 이용하는 문제를 해결해 보자.

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

이 문제를 어떻게 풀어야할까? 이 문제는 동적계획법을 이용하여 O(N²)에 풀 수 있다.

{10,20,10,30,20,50}의 수열에서 각각의 자리마다 현재까지의 가장 긴 증가하는 부분수열을 기록하여 가장 큰 값을 출력하면 그것이 가장 긴 증가하는 부분수열의 길이가 된다. 원리를 살펴보자.

총 6개의 값이 있으니 i=1부터 i=6까지 살펴보자.

먼저 기본적으로 길이를 계산할때 자기 자신을 포함하므로 각각의 DP값을 1로 설정하고 시작한다.

i=1, 10일때 10보다 먼저 나온 수가 없으므로 DP[1]=1을 기록하고 넘어간다.

i=2, 20일때 앞서 나온 수 중에 20보다 작은 10이라는 숫자가 있다. 따라서 DP[2]=DP[1]+1이 된다.

i=3, 10일때 10보다 작은 수가 없으므로 DP[3]=1을 기록한다.

i=4, 30일때 30보다 작은 수가 여러개 존재한다. 이 중에 가장 큰 값을 기준으로 +1 해주면 된다.

현재까지의 DP값중 가장 큰값은 DP[2]인 2이다. DP[2]역시 그 전까지 증가하는 수열의 길이만을 기록했으므로 20보다 큰 30은 그동안의 값중 가장 큰값인 DP[4]=DP[2]+1을 해주면 된다.

i=5, 20일땐 20보다 작은 숫자인 DP[1]또는 DP[3]의 값에 +1을 해주면 된다.

i=6, 50일땐 앞에 i=4의 경우와 같이 자신보다 작은 DP값중 가장 큰값에 +1을 해주면 된다. DP[6]=DP[4]+1이다.

이 후 DP에 저장된 값중 가장 큰 값이 주어진 수열내에 가장 긴 증가하는 부분수열의 길이가 될것이다.

C++로 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
int dp[1001];
int arr[1001];
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		dp[i] = 1;
	}

	int ans = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[i] > arr[j])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ans = max(ans, dp[i]);
	}

	cout << ans;
}

BOJ : 12015 가장 긴 증가하는 부분 수열2

그렇다면 위 문제도 살펴보자. 이 문제는 입력값으로 최대 1,000,000의 데이터가 주어진다. 따라서 위 알고리즘 처럼 동적계획법을 통해 O(N²)으로 푼다면 당연히 시간초과가 날것이다. 이 문제는 최소 O(NlogN)으로 풀어야만 시간초과를 피할 수 있다. O(NlogN)으로 풀기 위해서 우리는 lower bound에 대해 알아야 한다.

lower bound는 정렬된 배열중 임의의 값에 대해 값이 삽입될 수 있는 위치 중 가장 작은 인덱스를 가르킨다.

예를들어 [1,3,4,6]이라는 배열이 존재하고 이 배열에 3이라는 값을 삽입하고자 할때 lower bound는 3이 처음 등장하는 두번째 위치를 가르킨다. 이 작업은 O(logN)의 시간동안 수행되며 C++ STL에 내장되어 있다.

그렇다면 lower bound를 이용하여 위 문제를 해결해보자.

우리는 임의의 리스트를 하나 만들고 이 리스트에 lower bound를 이용하여 데이터를 추가할것이다.

과정은 다음과 같다. 리스트가 비어있다면 데이터를 하나 추가하고, 그 후부터 등장하는 수에 대해 리스트의 마지막 값보다 크면 리스트의 맨 뒤에 추가하고 리스트의 마지막 값보다 작다면 해당 리스트의 lower bound를 구하여 값을 덮어쓴다. 아래 과정을 통해 이해 해보자.

{10 20 10 30 20 50} 라는 수열이 있고 현재 리스트는 아무것도 들어있지 않다.

i=1, 10일때 리스트가 비어있으므로 값을 추가한다. List={10}이 된다.

i=2, 20일때 List의 가장 큰 값인 10보다 더 크므로 리스트의 마지막에 추가한다. List={10,20}이 된다.

i=3, 10일때 List의 가장 큰 값인 20과 비교한다. 더 작으므로 해당 값은 증가하는 부분 수열이 될 수 없다. 따라서 10의 lower bound를 구한다. lower bound는 1이므로(index는 1부터 시작한다 가정) 1의 자리에 10을 덮어쓴다.

따라서 List={10,20}이 된다. (덮어 쓰는 이유는 아래에 설명)

i=4, 30일때 List의 가장 큰 값인 20보다 크므로 뒤에 추가한다. List={10,20,30}이 된다.

i=5, 20일때 List의 가장 큰 값인 30보다 작으므로 lower bound를 구하고 덮어쓴다.

List={10,20,30}이 된다.

i=6, 50일때 List의 가장 큰 값인 30보다 크므로 마지막에 추가한다.

최종적으로 List에 남은 값은 {10,20,30,50}이 된다. 이 때 이 List의 크기인 4가 가장 긴 증가하는 부분수열의 길이가 된다.

(※주의. 해당 배열이 가장 긴 증가하는 부분수열은 아니다. 우리는 size를 통해 길이만을 알 수 있다.)

위 과정만을 본다면 우리가 lower bound를 통해 값을 덮어쓰는 과정이 의아할 수 있다. 아래 예시를 보자

{30,10,20,10,50}

우리는 먼저 30을 리스트에 추가할 것이다. List={30}

그리고 다음 숫자인 10을 볼때 10은 리스트에서 가장 큰 값인 30보다 작으므로 뒤에 추가할 수 없다.

그러나 lower bound를 통해 1번 index에 덮어써야한다. 만약 덮어쓰지 않는다면 우리는 10부터 시작하는 가장 긴 증가하는 부분수열을 확인할 수가 없다. 30뒤에 10이 나온순간 부터 30부터 시작하는 가장 긴 부분수열의 길이는 증가 할 수 없다. 따라서 값을 덮어쓰고 다음과정을 진행해야 한다. 또 위와 같이 덮어쓰는 과정을 거치기에 List에 남은 값이 가장 긴 증가하는 부분수열이 아닐 가능성이 존재하게 된다.

C++로 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	int N;
	cin >> N;
	vector <int> list;
	for (int i = 0; i < N; i++)
	{
		int val;
		cin >> val;

		if (list.empty() || list.back() < val) //리스트가 비어있고, 리스트의 가장 큰값보다 현재값이 크다면
		{
			list.push_back(val); //리스트의 뒤에 현재 값을 추가
		}
		else
		{
			auto pos = lower_bound(list.begin(), list.end(), val); //해당 값의 lower bound를 구함
			*pos = val; //해당 위치에 값을 덮어쓰기
		}
	}

	cout << list.size();
}

O(N²)와 O(NlogN) 의 LIS알고리즘을 살펴보았다.

위 알고리즘을 이용하여 BOJ : 14002 가장 긴 증가하는 부분 수열4 , BOJ : 14003 가장 긴 증가하는 부분 수열5 문제를 풀어보기 바란다. 힌트를 주자면 별도의 배열을 만들어 각 데이터의 lower bound를 기록하자.

이후 뒤에서부터 길이를 만족하는 인덱스의 값을 역순으로 출력하면 된다.

추가로 BOJ : 14002 가장 큰 증가 부분 수열 문제와 BOJ : 11054 가장 긴 바이토닉 부분 수열 문제도 풀어보자.

LIS알고리즘을 응용하여 해결할 수 있다.

[풀이]14003 가장 긴 증가하는 부분 수열5

[풀이]14002 가장 큰 증가 부분 수열

[풀이]11054 가장 긴 바이토닉 부분 수열