[Baekjoon] 11053 - 가장 긴 증가하는 부분 수열 (C++)

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

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

처음엔 꽤나 고민했던 문제였지만, DP(dynamic programming) 태그가 붙은 것을 보고 간단히 구현해서 풀 수 있었습니다. 이런 문제를 풀면서 느낀 게 DP 기법을 이용하면 복잡해 보이는 문제도 제법 간단한 코드로 구현할 수 있는 것 같더라고요. 생각보다 강력한 기법인 것 같습니다. 아직 DP에 익숙하지는 않아서 방법을 생각하기가 좀 어렵긴 하지만요... ㅎㅎ

 

어쨌든 이 문제의 핵심은 가장 긴 증가하는 부분 수열을 처음부터 한 번에 구하는 것이 아니라 차례대로 늘려가면서 구해야 한다는 점입니다. 앞에서부터 데이터를 계산해 가면서 나머지 데이터를 채우는 것이죠. 예를 들어 보겠습니다.

 

A[6]	10	20	10	30	20	50
DP[6]	1	0	0	0	0	0

먼저 A 수열이 위와 같이 되어 있다고 합시다. DP 배열은 A 배열의 대응되는 값까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이를 의미합니다. 예를 들어 DP[3] 값이 3인 경우 A[0]부터 A[3]까지의 값으로 만들 수 있는 가장 긴 증가하는 부분 수열의 길이가 3이라는 것을 의미합니다. 그러니 DP[0]의 값은 A[0] 하나만 있기 때문에 당연히 최대 길이는 1이 되겠죠? 이렇게 초깃값을 설정해준 뒤 나머지 데이터를 채워가면 됩니다.

 

A[6]	10	20	10	30	20	50
DP[6]	1	2	0	0	0	0

다음으로 DP[1] 값을 정해봅시다. 방법은 간단합니다. A[1]보다 이전에 있는 값 중에서 자신보다 작은 값만 선택합니다. 그 후 그 값과 대응되는 DP 값을 살펴보고 그중 최댓값을 골라서 1을 더한 뒤 DP[1]에 넣어주면 됩니다. 이렇게 하면 그때마다 가장 긴 증가하는 부분 수열의 길이를 구하게 되는 셈이므로 끝까지 모두 반복하게 되면 전체 수열에서 최댓값을 구할 수 있겠죠.

 

A[1] 값은 20입니다. 이전에 있는 값 중에서 자신보다 작은 값은 파란색으로 칠해진 10밖에 없으므로 그 DP 값인 1에 1을 더해서 2를 DP[1]에 넣어주면 됩니다.

 

A[6]	10	20	10	30	20	50
DP[6]	1	2	1	0	0	0

같은 방법으로 계속해서 진행해볼까요? A[2] 값은 10인데 이전에 있는 값 중에서 10보다 작은 값은 없습니다. 그러니 DP[2] 값은 1로 설정됩니다.

 

A[6]	10	20	10	30	20	50
DP[6]	1	2	1	3	0	0

A[3] 값은 30입니다. 이전에 있는 값이 모두 30보다 작으므로 전부 비교 대상이 됩니다. 그중에서 가장 큰 DP 값은 2이므로 DP[3]은 여기에 1을 더한 3이 됩니다.

 

A[6]	10	20	10	30	20	50
DP[6]	1	2	1	3	2	0

A[6]	10	20	10	30	20	50
DP[6]	1	2	1	3	2	4

끝까지 진행한 모습입니다. 이제 DP 배열에서 최댓값을 찾아주기만 하면 그 값이 바로 가장 긴 증가하는 부분 수열의 길이가 됩니다. 따라서 답은 4가 되는 것을 알 수 있습니다.

 

참고로 이 문제는 LIS(longest increasing subsequence)라는 꽤나 유명한 알고리즘 문제인 것 같더라고요. 위 방법으로 풀 경우 \( O(n^2) \) 시간 복잡도가 나오는데 \( O(n \log n) \) 시간 복잡도로 푸는 것도 가능하다고 하네요. 나중에 흥미가 생기면 한번 공부해보는 것도 재밌을 것 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> arr(n);
	vector<int> dp(n);
	int answer = 0;

	// 배열 데이터 입력
	for (int i = 0; i < n; i++) {
		int value;
		cin >> value;
		arr[i] = value;
	}
	
	// 초깃값 설정 (동적 계획법)
	// 수열의 데이터를 하나씩 늘려가면서 가장 긴 증가하는 부분 수열을 찾는 방식
	// 현재는 첫 번째 데이터만 있으므로 길이는 1
	dp[0] = 1;
	
	// 두 번째 데이터부터 수열에 추가하면서 부분 수열을 생성
	for (int i = 1; i < n; i++) {
		int maxLength = 1;
		
		// 이전에 만들어둔 길이 데이터(dp)와 비교하면서 가장 긴 수열을 찾음
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) maxLength = max(maxLength, dp[j] + 1);
		}
		
		// 길이 데이터 추가
		dp[i] = maxLength;
	}

	// 길이 데이터 중 최댓값 계산
	// 맨 마지막 데이터가 수열의 최댓값인 보장은 없기 때문
	for (int i = 0; i < n; i++) {
		answer = max(answer, dp[i]);
	}

	cout << answer << "\n";
	return 0;
}