(백준/C++) 11053_가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence) 문제는 동적 계획법을 활용하여 풀 수 있습니다.

동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.

동적 계획법 문제는 최적 부분 구조와 중복된 부분 문제의 두 가지 속성을 가진 문제에 유용합니다.

1. 최적 부분 구조: 가장 긴 증가하는 부분 수열(LIS)에서 현재 원소를 마지막 수로 하는 증가하는 부분 수열을 찾을 때, 현재 원소보다 작은 수를 마지막 수로 하는 수열의 최적 해로부터 최대 길이를 찾으면서 현재 문제의 최적해를 찾을 수 있습니다.
2. 중복된 부분 문제: 문제를 풀다 보면 같은 문제(특정 원소에서의 LIS 길이)가 여러 번 필요할 수 있습니다.
   동적 계획법에서는 이러한 중복된 부분 문제를 메모이제이션을 통해 한 번만 계산하고 결과를 저장하여 재활용함으로써 효율성을 높일 수 있습니다.

즉, 주어진 수열을 순차적으로 탐색하면서 각 위치에서의 가장 긴 부분 수열의 길이를 저장 해가며 풀어내는 문제입니다.

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

접근법

1. 초기화

이 문제는 초기화를 잘해야 합니다. 만약 각 요소를 첫 번째로 시작하는 부분 수열이라면 길이가 1이기 때문에 1로 초기화합니다.

2. 점화식 찾기

i번째 요소를 마지막으로 하는 가장 긴 증가하는 부분 수열을 찾으려면, i번째 요소보다 작은 모든 이전 요소(j < i)에 대해 가장 긴 부분 수열의 길이를 찾아야 합니다. (최적 부분 구조)

즉, 바로 이전의 수를 마지막으로 하는 수열이 가장 길다고 보장할 수 없기 때문에 모든 수열을 탐색합니다. (중복된 부분 문제)

---

풀이

이 문제는 접근법만 바라보면 단순한 문제처럼 보이는데, 처음에는 이해하기 어려운 문제일 수 있습니다.

동적 계획법으로 모든 상황에 대해 빠른 탐색을 원했다면, 2번 점화식 찾기에서 모든 수열을 탐색하는 부분을 외면하고 싶었을지도 모릅니다.

하지만, 저는 이전 작은 문제들에대해 각 요소에 대한 길이를 저장해 뒀다는 점에서 메모이제이션을 사용했다고 생각합니다.

따라서 다음과 같이 $O(N^2)$이라고 해도 동적 계획법으로 풀었다고 볼 수 있습니다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> seq;
vector<int> length;
int maxLength = 1;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
	seq.resize(N);
	length.resize(N, 1);

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

	//i까지의 수를 마지막으로 가지는 수열의 길이를 저장
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			//j까지를 마지막으로 하는 수열 다음에 i가 올 수 있는 경우 중 가장 큰 경우의 수를 저장한다.
			if (seq[i] > seq[j])
				length[i] = max(length[i], length[j] + 1);
		}
		//i 위치에서 가장 긴 수열의 길이를 갱신
		if (length[i] > maxLength) maxLength = length[i];
	}

	cout << maxLength;
}