백준 12015 [가장 긴 증가하는 부분 수열2]

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 출력하시오.

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

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

---

 이번 문제는 LIS(Longest Increasing Subsequence)문제이다. 이번 LIS는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 지금까지 LIS문제는 모두 DP를 이용하여 풀었었는데 이번 문제는 DP로 풀었더니 계속 시간초과가 발생하였다. DP를 이용하면서 할 수 있는 최적화는 다 해봤지만(중복 숫자 무시, 큰 숫자 무시 등) 결국 DP를 base로 푼 풀이들은 시간초과의 늪에서 탈출하지 못했다. 결국 이틀간 고민해본 끝에 푸는 방법에 대해 배워야겠다 생각해서 공부를 해보았다.

 

 공부를 해보니 LIS는 2가지 풀이법이 있는데 첫번째 풀이법 DP는 시간복잡도가 O(N^2)이고 두번째 풀이법 이분탐색을 이용한 풀이는 시간복잡도가 O(NlogN)이었다. 이번 문제는 두번째 풀이법인 이분탐색을 이용한 풀이를 사용해야 시간 초과가 나지 않고 풀리는 문제였다. 그러면 두번째 풀이법에 대해 한번 알아보자.

 

 만약 수열 A가 다음과 같이 주어졌다고 가정해보자 (다양한 case를 보기위해 일부러 복잡하게 만들었다)

i	0	1	2	3	4	5	6	7
A	40	20	30	10	15	25	30	5

이를 배열 X와 S에 순서대로 넣어보면서 답을 구해볼 예정이다.

 

규칙은 다음과 같다.

1. 수열 A의 0번째 값부터 차례로 판단에 들어간다 (이때 A의 값을 a라고 하겠다)

2. 배열 X가 오름차순일때 a가 들어갈 위치를 이진탐색으로 찾는다 (a가 들어갈 위치를 ai라 하겠다)

3. 찾은 ai값에 따라 다음 둘 중 하나를 실행한다.

     3 - a. 만약 X[ai]에 값이 아무 것도 없으면 X[ai]에 a를 대입하고 S[ai]의 값을 ai + 1로 한다.

     3 - b. 만약 X[ai]에 값이 존재하면 X[ai]에 X[ai]와 a중 더 작은 값을 대입한다.

4. 위 과정을 수열 A의 요소를 전부 다 돌때까지 반복한다.

5. 가장 큰 S값이 가장 긴 증가하는 부분 수열의 길이가 된다.

 

위 규칙에 따라 A[0]인 40부터 배열 X에 넣어보자.

 

(1)

i	0	1	2	3	4
X	40
S	1

처음은 간단하게 아무것도 없으므로 40을 X[0]에 넣는다.

 

(2)

i	0	1	2	3	4
X	20
S	1

두번째 요소인 20은 배열 X에 오름차순으로 들어가려면 0번 index에 들어가야 한다. 이때 X[0]에 40이 존재하므로 둘 중 더 작은 값인 20을 X[0]에 넣는다.

 

(3)

i	0	1	2	3	4
X	20	30
S	1	2

세번째 요소인 30은 오름차순으로 X에 들어가려면 맨 뒤 index인 X[1]에 들어가야하므로 X[1]에 넣어준다. 그리고 S[1]에는 2를 넣어준다. 

 

(4)

i	0	1	2	3	4
X	10	30
S	1	2

네번째 요소인 10은 오름차순으로 X에 들어가려면 0번 index에 들어가야 한다. 이때 X[0]에 20이 존재하므로 둘 중 더 작은 값인 10을 X[0]에 넣는다.

 

(5)

i	0	1	2	3	4
X	10	15
S	1	2

다섯번째 요소인 15는 오름차순으로 X에 들어가려면 1번 index에 들어가야 한다. 이때 X[1]에 30이 존재하므로 둘 중 더 작은 값인 15을 X[1]에 넣는다.

 

(6)

i	0	1	2	3	4
X	10	15	25	30
S	1	2	3	4

여섯번째, 일곱번째 요소인 25, 30은 오름차순으로 X에 들어가려면 맨 뒤 index인 X[2], X[3]에 들어가야하므로 X[2], X[3]에 넣어준다. 그리고 S[2]에는 3을, S[3]에는 4를 넣어준다. 

 

(7)

i	0	1	2	3	4
X	5	15	25	30
S	1	2	3	4

마지막 요소인 5는 오름차순으로 X에 들어가려면 0번 index에 들어가야 한다. 이때 X[0]에 10이 존재하므로 둘 중 더 작은 값인 5를 X[0]에 넣는다.

 

이렇게 A의 요소를 전부 사용해 만든 배열 X, S를 통해 가장 긴 증가하는 부분 수열의 길이를 알 수 있다.

이번 예제에서의 그 값은 배열 S의 최대값인 4가 된다. 하지만 배열 X에 나온 것처럼 가장 긴 증가하는 부분 수열이 {5, 15, 25, 30}인 것은 아니다. 실제로 길이가 4인 부분수열은 {10, 15, 25, 30}이다. 따라서 이 방법을 사용하면 부분 수열의 최대 길이는 알 수 있지만 그 부분 수열의 요소를 알 수는 없다. 아마 다른 기능을 추가하여 알고리즘을 업그레이드 하면 알 수있는 방법이 있겠지만 오늘은 여기까지만 알아보자.

 

 내가 이 문제를 풀기위해 작성한 코드는 다음과 같다.

import java.io.*;
import java.util.*;
class Main {
    static int binary_search(int[] X, int a, int r)
    {
        int l = 0;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (X[mid] >= a)
                r = mid;
            else
                l = mid + 1;
        }
        return (r);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] A = new int[n];
        int[] S = new int[n];
        int[] X = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            A[i] = Integer.parseInt(st.nextToken());
        int size = 0;
        for (int i = 0; i < n; i++)
        {
            int a = A[i];
            int ai = binary_search(X, a, size);
            if (ai == size)
            {
                X[ai] = a;
                S[i] = ai + 1;
                size++;
            }
            else if (X[ai] >= a)
             {
                    X[ai] = a;
                    S[i] = ai + 1;
            }
        }
        System.out.println(size);
     }
}

코드를 보면 위에서 설명한 내용과 비슷하다.

배열 A, X, S를 이용하여 부분 수열의 최대 길이를 찾는 것인데 이진탐색으로 lower_bound를 찾아 ai를 찾았고 위 규칙에있던 3-a, 3-b의 경우를 if절로 나눠 진행하였다. 이때 size를 이용하여 X와 S배열에 채워진 요소의 개수를 check하였고 이를 통해서 정답을 출력하기도 하였다.