[C++] BOJ 11053번 : 가장 긴 증가하는 수열 (LIS)

 

https://www.acmicpc.net/problem/11053

 

문제 1줄 요약

1. 수열 A의 가장 긴 증가하는 부분 수열을 구해라.

 

---

 

위와 같이 가장 긴 증가하는 부분 수열을

최장 증가 부분 수열, LIS(Longest Increasing Subsequence) 라고 한다.

 

LIS는

DP와 이분 탐색 두 가지 알고리즘을 활용하여 풀 수 있다고 한다.

 

이번 문제에서는

DP를 활용하여 풀어보고

다음 글에서는 가장 긴 증가하는 부분 수열 2를 이분 탐색으로 풀고자 한다.

 

 

가장 긴 증가하는 부분 수열은

문자 그대로 부분 수열이면서, 값이 점점 증가하는 형태를 띄고 있는 수열이다.

 

ex) 수열 A = {10, 20, 10, 30, 20, 50}의 LIS는?

{10, 20, 30, 50} 이 최장 증가 부분 수열이 될 것이다.

 

DP를 사용한다고 하면,

DP 테이블에 어떤 값들을 채워 나가야 할까?

 

https://www.youtube.com/watch?v=6QkmRvHMfqs

 

 

오늘은

문어박사 IT편의점 채널의 문제 풀이 영상을 참고하였다.

 

https://www.youtube.com/watch?v=6QkmRvHMfqs

 

 

수열의 값을 하나씩 체크할 것이다.

여기서 첫 번째 값인 10은 0 번째인 0과 비교한다는 가정으로

점화식을 보다 편리하게 작성할 수 있다.

 

수열의 값 하나를 택한 후

그 전까지의 수열의 값들을 비교해본다.

 

만일

4 번째의 수열의 값인 30을 비교할 차례라고 한다면,

그 앞까지의 10, 20, 10을 비교하는 것이다.

 

30보다 작은 값이라면, 이어지는 수열로 만들 수 있을 것이다.

반대로 30보다 크다면, 이전까지의 최대 값을 기반으로 새로운 수열을 만들게 된다.

 

의사 코드로 표현한다면 아래와 같겠다.

 

https://www.youtube.com/watch?v=6QkmRvHMfqs

 

 

위를 C++로 작성해보면 아래와 같이 작성할 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int A[1002];
int dp[1002];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int a;
    cin >> a;

    for(int i=1; i<=a; i++) cin >> A[i];

    for(int i=1; i<=a; i++)
    {
        int mx = 0;
        for(int j=0; j<i; j++)
        {
            if(A[i]>A[j])
                mx = max(dp[j], mx);
        }
        dp[i] = mx+1;
    }

    cout << *max_element(dp+1, dp+(a+1));
    return 0;
}

 

---

다음에는 이분 탐색으로

LIS 문제를 풀어보도록 하겠다!