[Algorithm] 최대 부분 증가수열(DP, LIS : Longest Increasing Subsequence)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제도 memorization을 활용하여 풀어내야 한다.

DP[N]은 N까지 수열이 주어질 때, 최대 부분 증가수열의 길이를 저장한다.

8

5 3 7 8 6 2 9 4

이 입력이로 주어진다면

아래와 같이 세팅이 될 것이다.

	1	2	3	4	5	6	7	8
arr	5	3	7	8	6	2	9	4
dp

먼저 5가 가장 뒤에 올 경우 증가 수열은 ( 5 ) 이므로

길이는 1이 된다.

	1	2	3	4	5	6	7	8
arr	5	3	7	8	6	2	9	4
dp	1

다음으로 3이 가장 뒤에 올 경우 증가 수열은 (3) 이므로 

마찬가지로 길이는 1이 된다.

앞에 5는 3보다 크므로 증가수열이 될 수 없다.

길이는 1이 된다.

	1	2	3	4	5	6	7	8
arr	5	3	7	8	6	2	9	4
dp	1	1

다음은 7이 가장 뒤에 올 경우 증가 수열은 (5, 7) 이거나 (3, 7) 이 될 수 있다.

5가 앞에 올 경우나 3이 앞에 올 경우 모두 길이가 2가 되므로 길이는 2

	1	2	3	4	5	6	7	8
arr	5	3	7	8	6	2	9	4
dp	1	1	2

다음 8이 가장 뒤에 올 경우,

앞에서 자신보다 작고 지금까지의 길이가 긴 숫자를 찾아본다.

바로 앞에 있는 7이 8보다 작고 원소들중에 가장 큰 길이를 갖는다.

그러므로 8은 arr[3] + 1 로 3이 된다.

	1	2	3	4	5	6	7	8
arr	5	3	7	8	6	2	9	4
dp	1	1	2	3

다음 6도 마찬가지로 

앞에 5와 3이 자신보다 작고 길이는 1이 최대이므로

2가 될 것이다.

이 동작대로 구현해보자.

#. Code

#include <cstdio>
#include <vector>
using namespace std;
#define MAX 2147000000
#define MIN -2147000000
 
vector<int> lst, dp;
int res = MIN;
 
void Process(int num, int pt)
{
    int i, length = 1, ans = MIN;
 
    for (i = 1; i <= pt; i++)
    {
        if (lst[i] <= num && dp[i] > ans)
            ans = dp[i];
    }
 
    dp[pt] = ans + 1;
 
    if (dp[pt] > res)
        res = dp[pt];
}
 
int main(void)
{
    int n, i;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    lst.resize(n+1, 0), dp.resize(n+1, 0);
 
    for (i = 1; i <= n; i++) 
        scanf("%d", &lst[i]);
 
    for (i = 1; i <= n; i++)
        Process(lst[i], i);
 
    printf("%d\n", res);
 
    return 0;
}

#. Teach code

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
 
    int n, res=0;
    cin>>n;
    vector<int> arr(n+1), dy(n+1);
 
    for(int i=1; i<=n; i++){
        cin>>arr[i];
    }
 
    dy[1]=1;
    for(int i=2; i<=n; i++){
        int max=0;
        for(int j=i-1; j>=1; j--){
            if(arr[j]<arr[i] && dy[j]>max){
                max=dy[j];
            }
        }
        dy[i]=max+1;
        if(dy[i]>res) res=dy[i];
    }
 
    cout<<res;
    return 0;
}

line 15) 직관적으로 구할 수 있는 작은 문제의 해를 미리 구해놓았다.

line 16~25) DP 처리 과정

line 18) 강사님께서는 역방향으로 탐색하였다.

line 19) 역방향 탐색을 하는 과정에서 현재 숫자보다 작고 길이가 max보다 길 경우,

max 값을 해당 숫자의 길이로 저장

line 23) 현재 숫자까지의 길이는 max + 1 이 될 것임

line 24) DP 과정에서 길이의 최댓값을 저장

#. Result

  - Input --------------------------------------------------------

8 

5 3 7 8 6 2 9 4

------------------------------------------------------------------

  - Output --------------------------------------------------------

4

------------------------------------------------------------------