[Algorithm] - LIS(Longest Increasing Subsequence)

Algorithm - LIS(Longest Increasing Subsequence)

코딩테스트 문제를 풀다보면 자주 마주치는 문제 알고리즘 유형에 대해 정리해보려고 한다.

첫번째로 정리할 내용은 **LIS(Longest Increasing Subsequence)**이다.

LIS(최장 증가 부분 수열) 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다.

LIS 란

LIS라는것은 한국말로 번역하면 최장 증가 부분수열이라고 할 수 있다.

말로만 하면 제대로 이해가 안될 수 있다.

예를 들어 설명하도록 하겠다.

아래와 같이 임의의 수열이 주어졌다고 하자.

위 수열에서 숫자 몇 개를 제거해서 아래와 같이 부분 수열을 만들 수 있다.

2 6 8 3

3 4 5 1

2 3 4 5

등등..

위와 같은 수열들 중 3번째 수열과 같이 수열 전체가 오름차순인 수열을 증가 부분 수열 이라고 할 수 있다.

한 수열에서 증가 부분 수열의 길이가 같다면 여러개의 LIS가 나올 수 있다.

이제 LIS의 길이를 구하는 방법을 알아보자.

LIS의 길이를 구하는 방법

시간 복잡도 : O(N^2)의 방법

반복문과 DP배열을 이용해서 구하는 방법이다.

위와 같은 수열이 있다.

앞에서부터 증가 수열을 찾으면서 DP에 수열의 길이를 기록 하자.

앞에 값 중 현재 값보다 작고, DP값에 저장된 수열의 길이가 가장 긴 값을 찾아야한다.

현재 값이 어떤 증가부분수열의 마지막 값이 되기 위해서는 증가부분수열의 마지막 값이 현재 값보다 작은 값이여야 한다.

따라서 현재 값을 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 현재 값이 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.

[2] : [2] → 길이 1 : 수열의 시작이므로 DP[0]에 1을 기록한다.

[6] : [2,6] → 길이 2 : 앞의 숫자 2가 현재 6보다 작으므로 DP[1]에 이전 DP값 + 1을 해준다.

[8] : [2,6,8] → 길이 3 : 앞의 숫자 6이 현재 8보다 작으므로 DP[2]에 이전 DP값 + 1 을 해준다.

[3] : [2,3] → 길이 2 : 앞의 숫자 8이 3보다 크므로 수열의 맨 앞에서부터 현재 값보다 작은 값을 찾아 그 값의 DP값에서 +1을 해준다

[4] : [2,3,4] → 길이 3 : 앞의 숫자 3이 현재 숫자 4보다 작고, DP 값이 2보다 크면서 숫자가 4보다 작은것이 없으므로 3의 DP값에 +1을 해준다.

[5] : [2,3,4,5] →길이 4 : 위와 같이 현재숫자보다 작으면서 DP값이 3보다 큰 것이 없으므로 4의 DP값에 +1을 해준다.

[1] : [1] →길이 1 : 현재 숫자보다 작은 값이 앞에 없으므로 DP에 1을 저장한다.

위의 과정을 통해 위 수열의 LIS의 길이는 4로 구할 수 있다.

위 알고리즘이 N^2의 시간 복잡도를 가지는 이유는, N개의 입력에 대해서 현재 값의 앞에 있는 값들을 전부 확인해야 하기 때문이다.

그다지 효율적인 알고리즘이라고 할 수는 없겠다.

아래는 코드로 표시한 부분이다.

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n;
	cin >> n;
	vector<int> nums(n,0); // 입력 값 저장 용도
	vector<int> lis(n,1); //현재숫자를 마지막으로 가지는 수열의 최대 길이 저장 용도
	for(int i =0; i < n; i++)
	{
        cin >> nums[i];
		for(int j =0; j < i; j++) // LIS 배열의 처음에서부터 현재값 바로 전까지 비교
		{
			if(nums[j] < nums[i])
			{
				lis[i] = max(lis[j] + 1,lis[i]); // 현재값보다 작으면서 길이가 가장 긴 수열에 뒤에 현재값을 넣는다.
			}
		}
	}
	cout << *max_element(lis.begin(),lis.end()) << "\\n";
}

 

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

위 문제는 방금 얘기했던 알고리즘으로 풀 수 있는 문제이다.

LIS길이 구하는 방법 중 좀 더 효율적인 것이 있다. 다음에 소개할 이진 탐색을 이용한 알고리즘이다.

시간 복잡도 : O(NlogN)의 방법 : lower_bound함수 사용(이진 탐색)

똑같이 위와 같은 수열이 있다.

LIS를 저장하기 위한 벡터를 하나 선언한다.

LIS벡터에 마지막 값이 현재 값보다 작다면 뒤에 현재 값을 붙이면 되고,

만약 크다면 lower_bound 함수를 통해 현재 값보다 크거나 같은 위치를 찾아 현재 값을 넣어준다.

기본적인 내용은 LIS 벡터의 같은 인덱스에 넣을 수 있는 값이 있다면 작은 값을 대신 채워 넣어주는 것이다.

아래 예제를 확인해보자.

LIS

[2] : [2] → 앞에 값이 없어 바로 벡터에 넣어준다.

[6] : [2,6] → LIS벡터의 마지막 값보다 현재 값이 크다. 벡터에 바로 넣어준다.

[8] : [2,6,8] → 위와 같다.

[3] : [2,3,8] → 여기서부터 위 알고리즘과 다르다. LIS벡터 중 이진탐색을 통해 현재 값보다 크거나 같은 위치(lower_bound) 하한값(6)을 찾아 해당 위치에 현재값(3)을 채워 넣어준다.

[4] : [2,3,4] → 4보다 크거나 같은 위치의 값이 8이고 해당 위치에 4를 채워 넣어준다.

[5] : [2,3,4,5] → LIS벡터의 마지막 값인 4보다 현재 값 5가 크다. 벡터에 바로 넣어준다.

[1] : [1,3,4,5] → 현재값 1보다 LIS벡터의 처음 값인 2보다 작으므로 2의 위치에 넣어준다.

위의 과정을 통해 나온 LIS 벡터 [1,3,4,5]는 최장 길이 부분 수열은 아니다.

LIS 벡터의 크기가 4라는 것은 알고리즘 과정 중에 LIS의 길이가 4인 최장 길이 부분 수열이 존재했다는 것을 의미한다.

위 내용은 LIS의 길이를 구하기 위한 알고리즘이라고 할 수 있다.

코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n,0);
    vector<int> lis;
    for(int i =0; i < n ; i++)
    {
        cin >> nums[i];
        if(lis.empty() || lis[lis.size()-1] < nums[i]) //lis벡터가 비어있거나, 마지막 값이 현재값보다 작을 경우에 현재값을 넣어준다.
        {
            lis.emplace_back(nums[i]);
        }
        else
        {
            auto iter = lower_bound(lis.begin(),lis.end(),nums[i]); //이진탐색을 lower_bound함수를 사용하여 현재값이 들어 갈 수있는 위치를 찾는다.
            *iter = nums[i]; //찾은 위치의 값에 현재값을 넣어준다.
        }
    }
    cout << lis.size() << "\\n";
}

 

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

위 문제는 방금 얘기했던 알고리즘으로 풀 수 있는 문제이다.

이 다음은 길이만 구하는 것이 아닌, 길이와 실제 최장 길이 부분 수열을 구하는 방법에 대해 알아보도록 하자.

 

추가 : LIS의 길이 및 수열 구하기 O(NlogN)

위의 코드에서 LIS 벡터의 현재 값의 이전 값의 위치를 기억하는 path 벡터와

LIS벡터 실제 값의 index를 기억하는 lisIndex벡터를 만든다.

위 예제로 실행해보도록 하겠다.

[2] 처음 [2]를 넣을때는 처음 값이므로 그냥 넣어준다. path에 -1을 넣는 이유는 제일 처음 값이라는 것을 표시하기 위함이다.

LIS : 2

Index : 0

path : -1

[6]

LIS : 2 6

Index : 0 1

path : -1 0

[8]

LIS : 2 6 8

Index : 0 1 2

path : -1 0 1

[3] → 앞의 값 중 6의 자리에 채워지면서 path의 현재 인덱스에 6이 원래 가리키던 2의 index 0을 넣어준다. 그리고 현재 2번째에 갱신된 3의 위치를 index에 갱신해준다.

LIS : 2 3 8

Index : 0 3 2

path : -1 0 1 0

이런식으로 쭉 가다보면

LIS : 1 3 4 5

Index : 6 3 4 5

path : -1 0 1 0 3 4 -1

이런식으로 나오게 되는데.. Index의 마지막 값은 현재 LIS 수열의 마지막 값의 인덱스를 의미한다.

마지막값의 인덱스를 path에 넣으면 이 전 값의 인덱스를 찾을 수 있다.

그렇게 뒤에서부터 쭉 찾아오게 되면 5→4→3→0→-1

실제 값은 5 4 3 2가 된다. 역순이므로 vector로 저장했다면 reverse함수를 사용해서 반전시켜서 리턴하면 되겠다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n,0);
    vector<int> lis; 
    //추가 부분
    vector<int> lisIndex;
    vector<int> path(n,-1);
    //
    for(int i =0; i < n ; i++)
    {
        cin >> nums[i];
        if(lis.empty() || lis[lis.size()-1] < nums[i]) //lis벡터가 비어있거나, 마지막 값이 현재값보다 작을 경우에 현재값을 넣어준다.
        {
            path[i] = lis.empty() ? -1 : lisIndex[lisIndex.size() -1]; //마지막 값을 가리키는 인덱스를 넣어준다.
            lis.emplace_back(nums[i]);
			lisIndex.emplace_back(i);
        }
        else
        {
            auto iter = lower_bound(lis.begin(),lis.end(),nums[i]); //이진탐색을 lower_bound함수를 사용하여 현재값이 들어 갈 수있는 위치를 찾는다.
            //추가부분
            int idx = iter - lis.begin();
            path[i] = idx == 0 ? -1 : lisIndex[idx-1]; //현재 값이 들어갈 lis의 이전 값을 가르킬수있도록 path에 넣어준다.
            lisIndex[idx] = i; // lisIndex에 현재 값이 있는 실제 위치를 저장
            //
           *iter = nums[i]; //찾은 위치의 값에 현재값을 넣어준다.
        }
    }
    cout << lis.size() << "\\n";
		//추가 코드 - 역추적(path 백터)을 통해 실제 LIS배열 출력
		int p = lisIndex[lisIndex.size()-1]; //lis의 마지막 값의 Index;
		stack<int> st_lis;
		while(p != -1)
		{
			st.lis.push(nums[p]); // lis 마지막 값을 넣어준다.
			p = path[p]; // path 벡터를 이용하여 이 전 lis 값의 index를 역추적한다.
		}

		while(st.empty() == false)
		{
			cout << st.top() << " ";
			st.pop();
		}
		cout << "\\n";
    //추가
}

 

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

위 문제는 위 코드처럼 LIS배열의 길이 및 실제 LIS배열을 출력하는 문제다.

위 코드를 분석하면 충분히 풀 수 있다.

이것으로 LIS 알고리즘에 대한 포스팅을 마치도록 하겠다.