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

 

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

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

 

---

 

문제 해결 과정

착안

이번 포스트에서 다루는 문제는 최장증가부분수열(longest incresing subsequence, LIS)을 구하는 문제인데, 이 문제는 다음과 같은 점들을 고려하여 효율적으로 해결할 수 있다.

 

$n$ 개의 항으로 이루어진 수열 $\{a_i\} \space (1 \leq i \leq n)$에 대하여, 증가부분수열들을 찾는 과정은 다음과 같다.

 

• 수열의 $k$ 번째 항 $a_k$에 대하여, $a_i \space (i=1, 2, ..., (k-1))$를 이용해 만든 증가부분수열 중 $a_k$보다 작은 수로 끝나는 증가부분수열이 존재하는 경우, 그 수열의 뒤에 $a_k$를 이어붙이면 길이가 1만큼 더 길고 $a_k$로 끝나는 새로운 증가부분수열을 만들 수 있다.

 

따라서 $k$ 번째 항까지의 증가부분수열 중, 가장 긴 부분수열을 만드려면 $k-1$ 번째 항까지의 증가부분수열 중에서 $a_k$보다 작은 수로 끝나며, 가장 긴 부분수열을 찾아 그 부분수열의 길이에 1만큼 더한 값을 $k$ 번째 항에 대한 최장증가부분수열 길이로 저장(동적계획법, dynamic programming)하는 방법으로 해결할 수 있다.

 

단, 위의 과정을 단순히 구현하면 $k$ 번째 항까지의 최장증가부분수열을 구할 때 $a_i \space (i = 1, 2, ..., (k-1))$ 번째 항들에 대한 최장증가부분수열을 모두 살펴보아야하므로 $O(n^2)$의 시간 복잡도를 필요로 한다.

 

따라서 $k$ 번째 항까지의 최장증가부분수열을 구함에 있어서, $i=1, 2, ..., (k-1)$ 번째 항까지의 최장증가부분수열을 모두 저장하는 대신 길이가 동일한 최장증가부분수열에 대해서는 끝나는 수가 가장 작은 경우만 저장하면, 이렇게 별도로 저장하는 배열은 증가부분수열의 끝나는 숫자에 대하여 항상 오름차순으로 정렬된 상태로 저장된다. 따라서 배열 내 요소를 탐색할 때 이진 탐색(binary search, 이분 탐색)을 적용할 수 있어 보다 효율적인 문제 해결이 가능하다.

* 참고) $1, 2, ..., k$ 번째 항까지의 최장증가부분수열에 대해, 같은 길이의 증가부분수열 중 끝나는 숫자가 가장 작은 경우만 저장하는 이유는 끝나는 숫자가 작을수록 이후 $i = k+1, ...$ 번째 항을 이어붙일 수 있는 가능성이 높기 때문이다.

 

구현

수열의 $k$ 번째 항 $a_k$에 대하여, $a_k$보다 앞에 있는 항들을 이용해 만든 최장증가부분수열의 (끝나는 숫자, 길이)를 저장할 배열을 선언하고, 편의상 초기값으로는 (끝나는 숫자 = 0, 길이 = 0)의 값을 넣는다.

 

이후 순차적으로 $a_i \space (i = 1, 2, ..., n)$이 입력될 때마다 아래와 같이 배열에 데이터를 추가하거나 최장증가부분수열 데이터를 갱신한다

 

$a_i$의 값을 입력받았을 때, 존재하는 증가부분수열의 뒤에 $a_i$를 이어붙일 수 있는 경우를 탐색해야하므로, 이진 탐색 알고리즘을 아래와 같이 구현한다(현재까지 만들어진 증가부분수열을 저장하는 배열: ISs[]).

 

• 시작 탐색 구간: $[0,$ ISs.size() $- 1]$
• 탐색 구간의 중간 부분에 해당하는 증가부분수열의 끝나는 숫자를 $a_i$와 비교,
  • 1) $a_i$가 더 큰 경우: 구간의 좌측 끝 값을 이동(middle + 1).
  • 2) $a_i$가 더 작은 경우: 구간의 우측 끝 값을 이동(middle - 1).
  • 3) $a_i$와 같은 경우: 탐색 종료 후 다음 수 입력 (최장증가부분수열을 만들 때 유의미하지 않은 경우이므로).

 

한편, 최장증가부분수열 데이터를 배열에 저장할 때 같은 길이의 증가부분수열 중에서 끝나는 숫자가 가장 작은 부분수열만 저장하므로, $a_i$보다 작은 수로 끝나는 증가부분수열 중 가장 긴 부분수열은 $a_i$보다 작은 수 중에서 가장 큰 수로 끝나는 증가부분수열이다. 따라서 해당하는 증가부분수열의 길이를 $l$이라고 하면, 길이가 $(l+1)$인 증가부분수열이

 

• 이미 배열에 존재하는 경우, 해당 수열이 $n$보다 큰 수로 끝나면 마지막 숫자를 $n$으로 교체한다.
• 배열에 존재하지 않는 경우, $n$으로 끝나는 $(l+1)$ 길이의 증가부분수열을 배열에 추가한다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

struct IS
{
	int LastNum;
	int Length;
};

vector<IS> ISs;

void Try_Append(int num)
{
	int left = 0, right = ISs.size() - 1;
	while (left <= right)
	{
		int middle = (left + right) / 2;
		if (num < ISs[middle].LastNum)
			right = middle - 1;
		else
			left = middle + 1;
	}
	
	if (ISs[right].LastNum < num)
	{
		if (left == (int)ISs.size())
			ISs.push_back(IS{ num, ISs.back().Length + 1 });
		else
			if (ISs[left].LastNum > num)
				ISs[left].LastNum = num;
	}
}

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

	ISs.push_back(IS{ 0, 0 });
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		Try_Append(num);
	}

	cout << ISs.back().Length << "\n";
	return 0;
}

 

실행 결과