DP LIS(최장증가수열) + 백준 문제 추천

사용언어

Visual studio 2019 C++

유형

다이나믹 프로그래밍 - LIS(최장증가수열)

최장 증가 수열 LIS(Longest Increasing Subsequence)

LIS란, DP에 존재하는 유형중에 하나이다.

간단하게 말하면 가장 긴 증가하는 부분 수열 이다.

만약 8의 길이를 가진 배열이 있다고 해보자

1 6 2 5 7 3 5 6

LIS를 찾는다면, 1 _ 2 _ _ 3 5 6 이렇게 5개가 선택된다.

즉, LIS는 앞에서부터 뒤로 숫자를 선택해서 부분 수열을 구성해 나갈 때 증가하는 순서대로 숫자를 고르면서 고른 부분 수열의 길이가 최대가 되도록 숫자를 선택하는 경우이다.

N이 10만이 넘지않는다면 시간복잡도가 O(N^2) 인 2중 for문으로 해결된다.

for (int i = 0; i < N; i++) {
	dp[i] = 1;
	for (int j = 0; j < i; j++) {
		if (arr[i] > arr[j]) {
			dp[i] = max(dp[j] + 1, dp[i]);
		}
	}
	many = max(many, dp[i]);
}

LIS 사용 문제

• 1965 상자넣기 - 위의 예시문제
• 11053 가장 긴 증가하는 부분 수열
• 11055 가장 큰 증가 부분 수열

[1965 풀이]

#include <iostream>
#include <algorithm>

#define endl "\n"
using namespace std;

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main() {
	int N;

	init();
	cin >> N;

	int* arr = new int[N];
	int* dp = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}

	int many = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = max(dp[j] + 1, dp[i]);
			}
		}
		many = max(many, dp[i]);
	}

	cout << many << endl;
}

[11053 풀이]

#include <iostream>
#include <algorithm>

#define MAX 1001
#define endl "\n"

using namespace std;

int N;

int main() {
	cin >> N;

	int* arr = new int[N];
	int* dp = new int[N];

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int many = 0;
	for (int i = 0; i < N; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j])
				dp[i] = max(dp[i], dp[j] + 1);
		many = max(many, dp[i]);
	}

	delete[] arr;
	delete[] dp;
	
	cout << many << endl;
}

[11055 풀이]

#include <iostream>
#include <algorithm>
#define endl "\n"

using namespace std;

int N;

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main() {
	init();
	cin >> N;

	int* arr = new int[N];
	int* dp = new int[N];

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int many = 0;
	for (int i = 0; i < N; i++) {
		dp[i] = arr[i];
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j])
				dp[i] = max(dp[j] + arr[i], dp[i]);
		many = max(many, dp[i]);
	}

	delete[] arr;
	delete[] dp;

	cout << many << endl;
}

참조링크: https://jason9319.tistory.com/113