[c++] Longest Increasing Sequence (문제 ID : LIS, 난이도 : 하) :: 알고리즘 문제 해결 전략 1권

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

문제

어떤 정수 수열에서 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

생각의 흐름

1. 원래 수열에서 1개 없애기, 2개 없애기, ... , n-1개 없애기까지 가면서 없앨 index의 조합을 모두 계산해보기

   조합 만들기가 너무 싫음 => 너무 복잡함..

2. 증가하는 최대구간찾기

   증가하는 부분수열 중 원래 수열에서 연속적으로 할당되어있는 것들을 조사한다.

   가장 큰 연속 부분수열을 택해서 앞 뒤로 더 작고 큰 수가 있는지 계산한다.

   반례 ) 연속적이지 않아도 가장 긴 증가부분수열이 나올 수 있음

   => test case 4번째

3. 각 index 이후에서 나올 수 있는 최대 증가수열의 길이를 저장해두기

   이후에 나올 index에 관계없이 각 index 마다 최선을 결정할 수 있는 최적부분구조이므로 재귀함수로 '완전탐색 + 다이나믹 프로그래밍' 구현할 수 있다.

주의할 점

1. 배열 등 객체의 size 함수를 for의 조건에서 쓰면 내부에서 변할 수 있으므로 이를 이용할 목적이 아니면 for문 들어가기 전에 다른 변수로 미리 받아두기

   int tmp = arr.size();
   for(int i=0; i<tmp; i++) // for(int i=0; i<arr.size(); i++) 하지말기

코드

#include <iostream>

using namespace std;
int N;
int arr[500];
int memorize[500];

int LIS(int index) {
    if (memorize[index] != -1)
        return memorize[index];
    else if (index == N - 1)
        return 1;
    int max = 1;
    for (int i = index + 1; i < N; i++) {
        if (arr[index] >= arr[i])
            continue;
        int tmp = LIS(i);
        if (max < 1 + tmp)
            max = 1 + tmp;
    }
    memorize[index] = max;
    return max;
}

int main() {
    int C;
    cin >> C;
    while (C--) {
        cin >> N;
        fill(memorize, memorize + sizeof(memorize) / sizeof(int), -1);
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
        int max = 0;
        for (int i = 0; i < N; i++) {
            int tmp = LIS(i);
            if (tmp > max)
                max = tmp;
        }
        cout << max << endl;
    }
}

test case (댓글 참고, 직접 만든 것들)

6
4
1 2 3 4 
8
5 4 3 2 1 6 7 8 
8
5 6 7 8 1 2 3 4
8
1 5 2 6 3 0 4 7
3
1 1 1
7
9 1 3 7 5 6 20

4
4
4
5
1
5

마지막 테스트 케이스가 안되는 경우

1. max가 나오는 경우를 한 번만 고려한 경우

   max 길이는 여러 번 나올 수 있으므로 각 경우에 대해 다 고려해주어야한다.

   ex_) 9 1 3 7 5 6 20 의 경우 연속된 수들 중 (1,3,7), (5,6,20) 두 개의 max 증가수열이 나온다.

2. 한 index에 대해서만 조사했을 경우

   완전 탐색으로 구현했을 경우 처음 index에서 남은 n-1개를 재귀함수로 탐색하는데, 이 때 index를 하나씩 증가시키면서 탐색해야한다.

   ex_) 0번째 원소에 대해 1~n-1번째 원소를 탐색 => 1번째 원소에 대해 2~n-1번째 원소를 탐색

   여기서 0번째 원소에 대해서만 구현하고 모든 index를 고려하도록 반복문 처리를 안해줬을 경우 해당 테스트케이스가 제대로 작동되지 않는다.

3. 더 빠른 해법

앞에서부터 배열에 넣으면서 증가수열이 아니게 될 때, 해당 수가 위치해야할 곳에 삽입해줌

해당 수가 위치해야할 곳은 이진탐색으로 찾기

시간복잡도가 O(nlgn)이다.

n : 처음부터 끝까지 시행

1 : 증가수열이 이어지는 지 확인

lgn : 이진탐색으로 삽입할 위치 찾기

코드 : https://jaimemin.tistory.com/317