[BOJ] 11053, 11722, 14002 LIS(가장 긴 증가하는 수열, 가장 긴 감소하는 수열) - 1

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

11053번: 가장 긴 증가하는 부분 수열

저는 바로 못풀었습니다. DP로 어떻게 풀지? 이렇게 생각했어요.

위키피디아에서 LIS를 검색해서 시뮬레이션을 보고 이분탐색으로 했습니다. 전 아이언5티어입니다..

​

풀이 방법 :

2가지가 있습니다. LIS 시리즈가 1~5까지 있는만큼, 더 좋은방법이 존재합니다.

이번 포스팅에서는 DP를 이용한 풀이, 다음 포스팅에서는 lower_bound를 이용한 풀이를 하겠습니다.

​

i번째 위치는 이미 k개만큼 증가한 수열이다. 라고 저장을 해두고 시작을 하는겁니다.

​

예시 : {1 5 6 2 3 4}

개수 : 1 2 3 2 3 4

여기서 6은 3개만큼 늘어나있잖아요? ( 1,5,6)

그럼 그 다음의 2는 뭘까요? (1,2) 가 될 수 있으므로 2 입니다.

그럼 그 다음의 3은? (1,2,3)이 될 수 있으므로 3 입니다.

그럼 마지막 4는? (1,2,3,4)가 될 수 있으므로 4 입니다.

​

이걸 코드로 표현하면 됩니다.

​

DP의 테이블을 정의해봅시다.

DP[i] = k // arr[i]는 arr[0] ~ arr[i-1]에 arr[i]보다 작은 수가 i를 포함해서 k개만큼 있다는 뜻입니다.

이게.. 코드를 보면 이해가 갑니다.

​

dp는 모두 1로 초기화 해주겠습니다. ( 1개만 있는경우 1개가 나와야 하니까요)

​

선택 정렬을 할때 보는 순서처럼 for문이 돌아갑니다.

for(int i = 1; i < n; i++)

for(int j = 0; j < i; j++) 이런식입니다.

​

증가하는 수열이어야 하므로 ( a[i] > a[j]) 현재 고정되어있는 i가 움직이는 j보다 커야 유의미 합니다.

​

예시 : arr[5] = {1, 5, 2, 3, 4} 로 해보겠습니다.

​

i = 0

dp[0] = 1;

​

i = 1

if( a[1] > a[0]) 이므로

dp[0] = 1;

dp[1] = 2; 입니다.

-> dp[i] = max(dp[i], dp[j] + 1)

dp[j]+1은, 이미 구해놓은 길이에서 1개를 더하겠다는 뜻입니다.

dp[i]가 필요한 이유는 i = 3일경우 알게 됩니다.

​

i = 2

dp[0] = 1;

dp[1] = 2;

dp[2] = 2; why? (a[3] > a[1]) 이라서 dp[i]에 dp[j]+1이 들어갔습니다.

​

i = 3

dp[0] = 1;

dp[1] = 2;

dp[2] = 2;

dp[3] = 3 why?

​

if(arr[3] > arr[0]) dp[3] = max(dp[3] , dp[0]+1); dp[3] = 2

if(arr[3] > arr[2]) dp[3] = max(2 , dp[2] +1) ; dp[3] = 3 입니다.

​

결국 다 끝나면, dp[i]가 max인 숫자를 return하면 최대 길이가 됩니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int arr[1005];
int dp[1005];
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,t,res = 0;	
	cin >> n;	
	for(int i = 0; i < n; i++)
	{
		cin >> arr[i];
		dp[i] = 1;
	}
	
	//0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
	for(int i = 1; i < n; i++)
	{
		for(int j = 0; j < i; j++)
		{
			if(arr[i] > arr[j])
			{
				dp[i] = max(dp[i], dp[j]+1); //dp[j]+1은 이미 개수 채워놓은거에서 숟가락 하나 더 얹기
			}
		}
	}
	cout << *max_element(dp,dp+n);
	// 내가 앞에원소보다 더커, 근데 그 위치가 이미 몇개보다 더 크면 그거 +1하면되고, 
	// dp
	
	
	return 0;	
}

시간 복잡도 : O(n^2)

​

저도 처음에 답을 보고도 뭐지? 싶었는데 한번 직접 해보니까 와닿았습니다.

​

이걸 해결하면

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

11722번: 가장 긴 감소하는 부분 수열

이것도 풀 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 1000005
int arr[MAX];
int dp[MAX];
vector<int> v;
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    int v_idx = 1;
    cin >> n;
    fill(dp,dp+n,1);
    
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(arr[i] < arr[j])
            {
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }
    cout << *max_element(dp,dp+n);
    
    return 0;
}

LIS의 개수는 구했는데, LIS를 출력하는 문제도 있습니다

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

14002번: 가장 긴 증가하는 부분 수열 4

이건 n = 1000이라서 통과할 수 있었습니다.

O(n^2)을 해도 됩니다. 하지만 다른문제는 n이 100만이라 불가능한 풀이입니다.

​

여러분이 dp를 구했죠?

예시 = {1,5,6,2,3,4}

dp는 그러면 이렇게 차있습니다

dp = {1,2,3,2,3,4}

​

여기서 앞에부터 출력하려고 하면 많이 꼬입니다. 2,3이 여러개라 뒤에 2,3을 출력해야 하는데.. 어떻게 하지? 싶습니다.

그냥 거꾸로 출력한다고 생각하면 됩니다.

​

vector<int> v에 for문을 거꾸로 돌려서 뒤에부터 넣어봅시다.

for(int i = n-1; i >= 0; i--)

{

  if( dp[i] == size){

    v.push_back(arr[i]);

    size--;

  }

}

이런식으로 해주면, 맨 뒤에부터 4,3,2,1의 원소들이 들어갑니다.

​

이걸 reverse를 해서 vector를 찍어줘도 되고, 그냥 vector를 뒤부터 출력해도 됩니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 1000005
int arr[MAX];
int dp[MAX];
vector<int> v;
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    int v_idx = 1;
    cin >> n;
    fill(dp,dp+n,1);
    
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(arr[i] > arr[j])
            {
                dp[i] = max(dp[j]+1, dp[i]);
            }
        }
    }
    int ans = *max_element(dp,dp+n);
    cout << ans << "\n";
    
    for(int i = n-1; i >= 0; i--)
    {        
        if(dp[i] == ans){
            v.push_back(arr[i]);
            ans--;
        }
    }
    reverse(v.begin(),v.end());
    for(auto i : v) cout << i << " ";

    return 0;
}

​

DP를 조금 더 학습했다고 생각하려고 합니다.

n이 클때는 풀 수 없습니다.

​

다음 포스팅에는 이분탐색으로 뵙겠습니다.