[알고리즘 문제해결전략] LIS - Longest Increasing Sequence

LIS 문제를 해결하는 방법은 두 가지가 있다.

1. 수열 중 LIS를 만족하는 모든 경우의 수 확인 + 메모이제이션 / 시간복잡도 (N^2)

2. LIS가 항상 순증가 한다는 특성을 활용한 방법 (길이가 i인 LIS 중 가장 유리한 LIS는 마지막 값이 최소인 LIS) / 시간복잡도 (NlogN)

 

1번 방식

[생각의 흐름]

1. 재귀 함수를 통해 모든 경우의 수를 구한다.

2. 부분문제로 정의 할 때 현재 수열에서(subsequence[startPosition]) LIS값을 구하는게 최적의 값

3. 메모이제이션을 통해 중복 된 계산을 제거

 

/* https://www.algospot.com/judge/problem/read/LIS */

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

using namespace std;

const int MAX_SIZE = 555;

int N;
int subsequence[MAX_SIZE];
int cache[MAX_SIZE];

int LIS(int startPosition)
{
    int &ret = cache[startPosition]; // 현재 startPosition에서 LIS 값을 cache에 저장

    if (ret != -1)
        return ret;

    ret = 0;
    for (int i = startPosition + 1; i < N; i++)
    {
        if (subsequence[startPosition] < subsequence[i]) // LIS조건을 만족하기 위해 subsequence[startPosition]보다 큰 값만 추가
        {
            ret = max(ret, LIS(i) + 1);
        }
    }

    return ret;
}

int main(void)
{
    int C;
    scanf("%d", &C);
    while (C--)
    {
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &subsequence[i]);
        }
        memset(cache, -1, sizeof(cache));

        int ret = 0;
        for (int i = 0; i < N; i++)
            ret = max(ret, LIS(i) + 1);
        printf("%d\n", ret);
    }
    return 0;
}

 

2번 방식

[생각의 흐름]

1. LIS문제는 LIS의 길이를 구하는 문제이기 때문에 모든 경우의 수를 볼 필요가 없다.

2. 길이가 i인 LIS의 경우의수 중 수열의 i번째 숫자가 가장 작은게 유리하다.

예) {1,2} {5,6} {5,7} 중 다음 LIS를 위해 유리한 LIS는 {1,2}이다.

3. 길이가 i일 때 수열의 i번째 수를 가장 작은 값을 vector에 저장한다.

4. vector의 size가 LIS가 된다.

 

/* https://www.algospot.com/judge/problem/read/LIS */

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

using namespace std;

int main(void)
{
    int C;
    int N;
    scanf("%d", &C);
    while (C--)
    {
        scanf("%d", &N);
        vector<int> LIS;

        for (int i = 0; i < N; i++)
        {
            int subsequence;
            scanf("%d", &subsequence);

            vector<int>::iterator lowPosition = lower_bound(LIS.begin(), LIS.end(), subsequence);
            // subsequence보다 같거나 큰 값중 가장 작은 값의 위치를 구한다

            int lengthOfLIS = lowPosition - LIS.begin();

            if (lengthOfLIS == LIS.size())
            {
                // subsequence보다 같거나 큰 값중 가장 작은 값의 위치가 없는 경우(LIS 끝에 값을 추가해야 하는 상황)
                LIS.push_back(subsequence);
                continue;
            }

            LIS[lengthOfLIS] = subsequence;
            // LIS 길이(lengthOfLIS) 중 끝 값이 가장 작은 값으로 업데이트 한다.
        }
        printf("%u\n", LIS.size());
    }
    return 0;
}