[알고스팟] 최장 증가 부분 수열 LIS (longest increasing subsequence)

문제링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • LIS
  • 2000ms
  • 65536kb
  • 11527
  • 3146 (27%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.

어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.

출력

각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.

예제 입력

3
4
1 2 3 4
8
5 4 3 2 1 6 7 8 
8
5 6 7 8 1 2 3 4

예제 출력

4
4
4

어떻게 풀까?

동적 프로그래밍에서의 대표적인 문제 LIS (longest increasing subsequence)입니다.

해당 문제는 O(n * log n)의 해결 방법이 있습니다.

우선, 배열의 길이만큼 추가 배열을 하나 만듭니다. (memoi[size] 라고 하겠습니다.)

그리고 memoi[i] 에는 i번에 들어갈 수 있는 수 중에서 가장 작은 수 가 들어가게 됩니다.

배열의 개수가 n개이고, 배열이 LIS의 어디부분에 들어가는지 찾는 부분에서 바이너리 서치를 이용하게 되므로

총 걸리는 시간은 O(n * log n)이 되는 것입니다!

프로그램으로 동작시키는 방법은 다음과 같습니다.

1. 수를 읽어서 LIS에 저장된 값 중에서 그 수보다 크거나 같은 값 중에서 가장 왼쪽에 있는 위치를 구합니다. (lower bound)

2. 해당 위치에 수를 넣습니다. 만약, LIS의 최대 길이가 증가했다면 갱신합니다.

3. LIS의 크기를 반환합니다.

과연 이것이 정당한 방법인지 예를 통해 살펴봅시다.

만약, 주어진 현재 만들어진 LIS가 2, 10, 12 라고 합시다.

이 다음에 5가 들어오면 LIS는 2, 5, 12가 될 것 입니다.

그리고 7과 8이 들어오면 LIS는 2, 5, 7, 8이 될 것 입니다.

해당 위치에 있는 수 보다 작은 수로 최신화되기 때문에 현재 LIS에는 영향을 주지 않고, 다음에 들어올 수 있는 수가 입력되었을 때, 이를 놓치지 않게 해주는 것입니다.

그림을 통해 살펴봅시다.

처음에 LIS의 크기가 0이기 때문에 바로 들어갑니다.

4 < 5 이기 때문에, 5의 위치를 4가 뒤집어 씁니다.

3 < 4 이기 때문에, 4의 위치를 3이 뒤집어 씁니다.

2 < 3이기 때문에, 3의 위치를 2가 뒤집어 씁니다.

1 < 2 이기 때문에, 3의 위치를 2가 뒤집어 씁니다.

가장 큰 수가 들어왔기 때문에 LIS의 길이가 1 증가합니다.

가장 큰 수가 들어왔기 때문에 LIS의 길이가 1 증가합니다.

가장 큰 수가 들어왔기 때문에 LIS의 길이가 1 증가합니다.

모든 LIS를 구했고, 답은 최장 증가 부분 수열의 길이는 4가 됩니다.

코드

// 최대 증가 부분 수열
// 알고스팟
// https://algospot.com/judge/problem/read/LIS
 
#pragma once
#include<cstdio>
#include<cstring>
 
int t, arr[500], n;
int res[501], rIdx;
 
//바이너리 서치
//현재 lis 수열이 완성된 곳에서 현재 입력된 값보다 크거나 같은 곳의 위치 반환
int bs(int v)
{
    int m;
    int l = 0, r = rIdx;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (res[m] >= v)
        {
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
 
    return r + 1;
}
 
void init()
{
    memset(res, 0, sizeof(res));
    rIdx = 0;
    scanf("%d\n", &n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d \n", &arr[i]);
    }
}
 
int LIS()
{
    scanf("%d\n", &t);
    while (t--)
    {
        init();
        for (int i = 0; i < n; i++)
        {
            int idx = bs(arr[i]);
            rIdx = rIdx < idx ? idx : rIdx;
 
            res[idx] = arr[i];
        }
 
        printf("%d\n", rIdx);
    }
    return 0;
}