[백준 C++] 11053, 12015 가장 긴 증가하는 부분 수열 1, 2

가장 긴 증가하는 부분 수열 1

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

가장 긴 증가하는 부분 수열 2

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

 

자료 출처

1. [최장 증가 수열] LIS(Longest Increasing Subsequence)

2. cppreference

 

문제 유형 : DP, 이분 탐색

 

크기가 N인 수열이 있을 때 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이고, 길이는 4이다.

 

가장 긴 증가하는 부분 수열 1과 2의 조건의 차이점은 다음과 같다.

 

	1	2
수열 A의 크기(N)	1 ≤ N ≤ 1,000	1 ≤ N ≤ 1,000,000
$A_i$의 크기	1 ≤ $A_i$ ≤ 1,000	1 ≤ $A_i$ ≤ 1,000,000

 

즉, 2번 문제를 풀 때 좀 더 효율적인 알고리즘이 필요하다.

 

가장 긴 증가하는 부분 수열 1

 

1번 문제는 DP로 풀었다. dp[i]를 'arr[0]...arr[i]에서 arr[i]를 포함하는 가장 긴 증가하는 부분 수열의 길이'라고 정의하자. dp[i]는 다음 것들의 합이다.

 

(여기서 j는 0...i - 1이다.)

 

1. 자기 자신의 길이( = 1 )

2. arr[i] > arr[j]를 만족하는 dp[j] 중 최댓값

 

위에 나왔던 것을 예로 들어보자. 

 

A = {10, 20, 10, 30, 20, 50}

 

1. 영 번째 원소인 10은 자기 자신보다 작은 원소가 없으므로 2번의 경우는 패스한다. 자기 자신만 있으므로 dp[0] = 1이다.

2. 첫 번째 원소인 20은 자기 자신보다 작은 원소가 {10}이다. 20은 자기 자신보다 작은 원소가 {10}이므로 dp[0] = 1이다. 자기 자신을 더하면 dp[1] = 2이다.

3. 두 번째 원소인 10은 자기 자신보다 작은 원소가 없으므로 2번의 경우는 패스한다. 자기 자신만 있으므로 dp[2] = 1이다.

4. 세 번째 원소인 30은 자기 자신보다 작은 원소가 {10, 20, 10}이다. 이 중 dp[j]가 가장 큰 것은 dp[1]인 2이다. 자기 자신을 더하면 dp[3] = 3이다.

5. 네 번째 원소인 20은 자기 자신보다 작은 원소가 {10, 10}이다. 이들의 dp[j] = 1로 동일하다. 자기 자신을 더하면 dp[4] = 2이다.

6. 다섯 번째 원소인 50은 자기 자신보다 작은 원소가 {10, 20, 10, 30, 20}이다. 이 중 dp[j]가 가장 큰 것은 dp[3] = 3이다. 자기 자신을 더하면 dp[5] = 4이다.

 

	0	1	2	3	4	5
A[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	4

 

dp 중 가장 큰 것이 가장 긴 증가하는 부분 수열이므로 4가 정답이다.

 

그렇다면 이 알고리즘은 어떻게 문제를 해결할 수 있을까?

 

다음과 같은 조건을 만족하면 된다.

 

• dp[i]가 자기 자신을 포함한 가장 긴 증가하는 부분 수열의 길이어야 한다는 점

dp[0]...dp[i - 1]은 자기 자신을 포함하는 가장 긴 부분 수열의 길이다. 만약 arr[i] > arr[j]라면 증가 수열의 원소들보다 arr[i]가 더 크다는 말이므로 d[i] = d[j] + 1이라는 식이 증가하는 부분 수열이라는 조건이 무너지지 않는다.

 

#include <stdio.h>
using namespace std;
#define SIZE 1000
#define FOR(i, N) for (int i = 0; i < N; i++)
int arr[SIZE];
int dp[SIZE];

int main() {
  int n, max = -1;
  scanf("%d", &n);

  FOR(i, n) scanf("%d", &arr[i]);
  FOR(i, n) {
    dp[i] = 1;
    FOR(j, i) {
      if (arr[i] > arr[j] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
    }
    if (max < dp[i]) max = dp[i];
  }
  printf("%d", max);

  return 0;
}

 

가장 긴 증가하는 부분 수열 2

 

시작하기 전에 1번 문제에서 작성했던 알고리즘의 문제점을 짚고 넘어가자.

 

1번 문제의 시간 복잡도를 결정하는 부분은 이중 반복문 안에 위치한 line 16이다. 최악의 경우, 즉, A[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}와 같이 증가하는 수열을 이룰 때, 모든 i, j 마다 dp[i] 값을 업데이트 해줘야 한다. 이 경우에는 시간 복잡도가 O($N^2$)이다. 1번 문제와 같이 N의 범위가 1,000까지인 경우에는 O($N^2$)으로 해결해도 문제가 없지만, 2번 문제와 같이 N의 범위가 1,000,000까지인 경우에는 똑같은 소스코드를 제출하면 시간 초과를 받는다.

 

그래서 2번 문제에서는 이분 탐색을 활용해 문제를 해결한다. 결론부터 말하자면 O($NlogN$)의 시간 복잡도로 문제를 해결할 수 있다.

 

먼저 가장 긴 부분수열을 저장하는 벡터 v를 만들자. 그리고 arr[0]...arr[i]를 순회하면서 v에 삽입한다. 삽입하는 방법은 다음과 같이 나뉜다.

 

1. v가 비어 있거나, arr[i]가 v의 마지막 값(back)보다 클 때 arr[i]를 v에 push한다.

2. 1이 아니라면 lower_bound를 찾아서 그 위치에 있는 원소를 arr[i]로 대체한다. (lower_bound는 범위에서 삽입되는 arr[i]보다 크거나 같은 첫번째 원소의 iterator를 반환한다)

 

예를 들어보자. 

 

A = {10, 20, 40, 25, 20, 50, 30, 70, 85}

 

1. v가 비어 있으므로 10을 push한다. v = {10}

2. 20은 v.back()인 10보다 크므로 push한다. v = {10, 20}

3. 40은 v.back()인 20보다 크므로 push한다. v = {10, 20, 40}

4. 25는 v.back()인 40보다 작으므로 lower_bound를 찾는다. v에서 25보다 크거나 같은 첫 번째 원소는 v[2]이므로 v[2] = 25이다. v = {10, 20, 25}

4. 20은 v.back()인 25보다 작으므로 lower_bound를 찾는다. v에서 20보다 크거나 같은 첫 번째 원소는 v[1]이므로 v[1] = 20이다. v = {10, 20, 25}

5. 50은 v.back()인 25보다 크므로 push한다. v = {10, 20, 25, 50}

6. 30을 v.back()인 50보다 작으므로 lower_bound를 찾는다. v에서 30보다 크거나 같은 첫 번째 원소는 v[3]이므로 v[3] = 30이다. v = {10, 20, 25, 30}

7. 70은 v.back()인 30보다 크므로 push한다. v = {10, 20, 25, 30, 70}

8. 85은 v.back()인 70보다 크므로 push한다. v = {10, 20, 25, 30, 70, 85}

 

v의 사이즈는 6이므로 가장 긴 증가하는 수열의 길이는 6이다.

 

정리해보자면 1번 알고리즘과 2번 알고리즘의 차이점은 다음과 같다.

 

	1번	2번
외부 FOR문	O(N)	O(N)
내부 FOR문	O(N)	O(logN)
최종 시간 복잡도	O($N^2$)	O(NlogN)

 

1번 알고리즘에서는 i가 0...N을 순회하면서 dp[i]를 채워넣는 외부 FOR문이 있고, j가 0...i - 1을 순회하면서 dp[i]에 넣을 값을 결정하는 내부 FOR문이 있다. 이들의 시간 복잡도는 각각 O(N)이기 때문에 최종 시간 복잡도가 O($N^2$)가 되는 것이다.

 

반면 2번 알고리즘에서는 i가 0...N을 순회하면서 arr[i]를 v의 끝에 삽입할지 혹은 v 내부의 특정 위치에 있는 원소와 대체할지를 결정하는 외부 FOR문이 있고, 후자의 경우에는 위치를 정하는 lower_bound가 있다(사실 이 부분은 FOR문이 아니다). 이 때 외부 FOR문은 O(N)의 시간 복잡도를 가지며, lower_bound는 O(logN)의 시간 복잡도를 가진다. 그렇기 때문에 최종 시간 복잡도가 O(NlogN)이 되는 것이다.

 

하지만 여기서 주의할 것이 있다. lower_bound가 빠르다고 해서 아무 곳에 사용해서는 안된다. lower_bound는 범위 내에 있는 원소들이 정렬되어 있다는 전제 하에 이분 탐색을 하기 때문에 O(logN) 안에 탐색을 완료할 수 있으므로 원소들이 정렬되어 있는지 확인해야 한다. (이 알고리즘은 v가 증가하는 수열이므로 정렬되었는지 여부는 굳이 확인할 필요가 없다.

 

그렇다면 이 알고리즘은 어떻게 문제를 해결할 수 있을까?

 

다음과 같은 조건을 만족하면 된다.

 

• v가 가장 긴 증가하는 수열이라는 점

v가 비어 있는 경우에는 arr[i]를 push한다. 원소가 하나 있으면 그것은 증가하는 수열로 간주한다.

 

arr[i]가 v에서 가장 큰 v.back()보다 큰 경우에는 v에는 arr[i]보다 큰 원소가 없다는 뜻이므로 v에 push한다. 그러면 증가하는 수열이라는 조건을 유지한다.

 

arr[i]가 v.back()보다 작은 경우에는 lower_bound를 찾아 해당 원소를 arr[i]로 대체한다. lower_bound는 arr[i]보다 크거나 같은 첫번째 원소를 가리키므로 그 원소를 arr[i]로 대체하면 arr[i]의 앞부분은 arr[i]보다 작고, arr[i]의 뒷부분은 arr[i]보다 크다. 그러므로 증가하는 수열이라는 조건이 무너지지 않는다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define FOR(i, N) for (int i = 0; i < N; i++)
vector<int> v;
int main() {
  int N, x;
  scanf("%d", &N);
  FOR(i, N) {
    scanf("%d", &x);
    if (v.empty() || v.back() < x) {
      v.push_back(x);
    } else {
      auto iter = lower_bound(v.begin(), v.end(), x);
      *iter = x;
    }
  }
  printf("%d", int(v.size()));
  return 0;
}