LIS 알고리즘 (1)

⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡·2021년 5월 18일

가장 긴 증가하는 부분 수열 (LIS) - 1

LIS 길이 구하기 (dp)

백준 11055 가장 큰 부분 증가 수열

LIS 길이 구하기 (이분 탐색)

백준 1365 꼬인 전깃줄

LIS 길이 문제:
백준 1965 상자 넣기
백준 11053 가장 긴 증가하는 부분 수열

LIS 길이 구하기 (dp)

LIS 길이를 구하는 가장 기본 코드이므로 익혀두기
dp[i] : i번째 수를 마지막 원소로 가지는 LIS의 길이

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int dp[1001] = { 0 };
	int A[1001] = { 0 };

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];

	int max = 1;
	dp[0] = 1;

	for (int i = 1; i < n; i++) {
		dp[i] = 1;

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

	cout << max;
	return 0;
}

백준 11055 가장 큰 부분 증가 수열

https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-11055-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EB%B6%80%EB%B6%84-%EC%A6%9D%EA%B0%80-%EC%88%98%EC%97%B4

➖

LIS 길이 구하기 (이분 탐색)

벡터 생성 -> 나올 수 없는 가장 작은 값을 삽입한다
벡터의 맨 뒤 원소와 A 비교
-> A 가 더 클 경우 벡터에 push_back() 해준 뒤 LIS의 길이 1 증가
-> A 가 더 작을 경우 lower_bound() 를 이용하여 최적의 자리를 찾은 뒤 그 자리의 값을 A로 교체한다
이때, 벡터에 들어있는 값이 LIS를 이루는 요소와 무관하다
수열 상에서 뒤에 위치한 원소가 앞에 위치한 원소보다 lower_bound로 탐색 된 최적의 위치가 앞에 있을 수도 있기 때문이다
예. 1 6 2 5 7 3
vt: 1
vt: 1 6
vt: 1 2
vt: 1 2 5
vt: 1 2 5 7
vt: 1 2 3 7
(LIS: 1 2 5 7)

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	int lis = 0;
	vector <int> vt;
	vt.push_back(INT_MIN);

	for (int i = 0; i < n; i++) {
    	int A;
		cin >> A;
		if (vt.back() < A) {
			vt.push_back(A);
			lis++;
		}
		else {
			auto it = lower_bound(vt.begin(), vt.end(), A);
			*it = A;
		}
	}

	cout << lis;
	return 0;
}