증가하는부분수열(Longest Increase Subsequence)

동적 계획법에 대한 예 중에 대표적인 것이 증가하는 부분 수열 문제이다. 

감소하는 부분 수열 문제 역시 둘 다 똑같은 개념이라고 할 수 있겠다. 

예를 들어 

수열

10, 20, 40, 30, 70, 50, 60이 있다고 한다면

이 중에서 증가하는 부분 수열 중에 가장 긴 것을 찾아라. 

라는 것이 증가하는 부분 수열이라고 하겠다. 

-----n^2 방법--------

간단히 n^2으로 풀 수 있는 소스를 설명하자면, 

(이 부분도 간단히 생각해내기 어려웠다. 동적계획법으로 푸는 n^2 이다)

정말 간단하고 쉬운 방법은 n! 완전탐색이겠다. 

#include <iostream>
using namespace std;
 
int arr[7] = { 10, 20, 40, 30, 70, 50, 60 };
int dy[8];
int n = 7;
 
int main(){
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < i; j++){
            if (arr[j] < arr[i] && dy[i] < dy[j] + 1){
                dy[i] = dy[j] + 1;
            }
        }
    }
        sort(dy, dy + n);  // 중요
    cout << dy[n - 1] << endl;
 
    return 0;
}

10, 20, 40, 30, 70, 50, 60

기준이 되는 i값을 빨간색, 

그 앞의 값들 j값들을 주황색으로 표현해서 설명하자면, 

(1) i = 1 일 때

10, 20, 40, 30, 70, 50, 60

=> dy[7] = {0, 1, 0, 0, 0, 0, 0};

(2) i = 2일 때

10, 20, 40, 30, 70, 50, 60

=> dy[7] = {0, 1, 2, 0, 0, 0, 0};

(3) i = 3일 때

10, 20, 40, 30, 70, 50, 60

=> dy[7] = {0, 1, 2, 2, 0, 0, 0};

(4) i = 4일 때

10, 20, 40, 30, 70, 50, 60

=> dy[7] = {0, 1, 2, 2, 3, 0, 0};

(보충설명) 70이 가지는 증가하는 부분 수열 10, 20, 40, 70이다. 

.......

써보면서 알게 되었는데, 최대 증가하는 부분 수열은 연속된 것을 고려하지 않는 듯 하다. 

연속 된 것을 찾기 위한 알고리즘은 아닌 듯 하다. 

20보다 작은 인덱스들을 처음부터 돌아다니면서 

20보다 작고 (arr[i] > arr[j]) ,현재 자신이 가지고 있는 증가수열의 개수보다 크면(dy[i] < dy[j] + 1) 

갱신

.....

Sort(정렬)를 반드시 해야 한다. 

대충 감이 올지 모르겠다. 나도 글을 써보니까 이해가 될 듯 하다. 

-----n*logn 방법--------

1)Lower Bound 방법

Lower Bound란 허용되는 하한값을 가진다는 것을 말한다. 

결국 입력 되는 값들을 고대로 인덱스로 가지면서 연산을 해주면 된다는 것이다. 

#include <iostream>
using namespace std;
 
int arr[5] = {5, 2, 4, 1, 3};
int dy[110000];
int n = 5;
 
int main(){
    for (int i = 0; i < n; i++){
        dy[arr[i]] = dy[arr[i] - 1] + 1;
    }
    for (int i = 0; i < 5; i++){
        cout << dy[arr[i]] << " ";
    }
    cout << endl;
    return 0;
}