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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

나의 풀이

이 문제는 lower_bound를 사용하여 푸는 문제로 한 번도 사용해보지 않아 검색을 통해 알아보았다.

우선 lower_bound란, 이진 탐색을 기반으로 찾으려는 값을 찾는 것은 동일하지만 찾으려는 값이 없다면 찾으려는 값보다는 큰 값들 중 가장 작은 값을 반환해주는 알고리즘입니다. 이진 탐색을 기반으로 하니 배열은 당연히 정렬이 되어 있어야 합니다. C++에는 lower_bound를 STL에서 기본으로 제공해준다고 합니다. 파이썬에는 없길래 직접 구현해보았습니다.

파이썬으로 lower_bound를 직접 구현해보았는데, 기존 이진 탐색을 구현하던 것과 코드가 매우 비슷하지만 start와 end가 같을때는 비교를 안해도 된다는 것과 찾으려는 값이 mid의 값보다 작다면 end를 mid - 1이 아닌 mid를 넘겨준 다는 것입니다. 여기서 mid에서 1만큼 빼주지 않는 이유는 찾으려는 값이 없다면 그 것보다 큰 값을 넘겨야하므로 mid값을 계속 가지고 있어야합니다. 코드로 보면 아래와 같습니다. 쉽게 말해 arr의 index값을 받아 n의 범위에 따라 찾아들어가면서 없는 상태에서 start와 end가 같아진다면 end를 반환해주면 n보다 큰 수 중 가장 작은 수를 가르키게 된다는 것입니다. 물론 start와 end가 같을때를 비교해보지 않으므로 이 과정에서 n과 mid의 값이 같을 수도 있습니다. lower_bound에서 중점은 n이 없다면 그보다 큰 수중 가장 작은 수를 찾는 것이니까요.

def lower_bound(arr, start, end, n):
    while start < end:
        mid = (start + end) // 2

        if arr[mid] < n:
            start = mid + 1
        else:
            end = mid
    return end

lower_bound의 예를 살펴보자면 다음과 같습니다.

** arr = [10, 20, 50, 60, 100]에서 n이 15로 주어질 때
1. lower_bound(arr, 0, 4, 15)
2. 0 < 4이므로 mid = 2, arr[2] = 50 > 15
3. end = 2
4. 0 < 2이므로 mid = 1, arr[1] = 20 > 15
5. end = 1
6. 0 < 1이므로 mid = 0, arr[0] = 10 < 15
7. start = 1
8. start == end (1 == 1)이므로 return 1
9. arr[1] = 20, 따라서 arr에서 15보다 큰 수들 중 가장 작은 값은 20이 된다.

lower_bound에 대해 알아보았으니 이제 이 문제에 대한 풀이를 해보겟다. 이 문제는 11053번 가장 긴 증가하는 부분 수열 문제의 시간복잡도를 줄이는 문제로 볼 수 있다. 11053번 문제에서는 dp를 사용해 문제를 풀었다. 살짝 코드를 보면,

for (int i=1; i<=n; i++) {
  dp[i] = 1;
  for (int j=1; j<=i; j++) {
    if (seq[i] > seq[j]) dp[i] = Math.max(dp[i],dp[j]+1);
  }
  answer = Math.max(answer,dp[i]);
}

위에와 같은데 주어지는 배열의 원소들을 하나하나 살펴보며 그 원소보다 앞에 있는 원소들에 대해 모두 접근해야한다. 그래서 시간복잡도는 O(N^2)이 됩니다. 그러나 이 문제는 주어지는 배열의 크기가 1,000이 아닌 1,000,000으로 O(N^2)의 시간복잡도를 가지면 시간초과가 발생하게 됩니다. 그래서 lower_bound를 사용하여 앞의 모든 수들을 보지않고 이진탐색을 하게 되면 시간복잡도는 O(logN)이 되면서 전체적인 배열의 값들을 살펴보게 되면 O(NlogN)으로 O(N^2)보다 빠르게 답을 찾을 수 있게됩니다.

시간 복잡도에 대해 생각을 해보았으니 이 문제를 풀어보겠습니다. 우선 배열을 입력받고 배열의 원소들을 앞에서 부터 하나하나 살펴봅니다. 그리고 하나의 빈 answer이라는 배열을 만들어놓고 가장 긴 증가하는 수열을 만들어갑니다.

1. 입력받은 배열의 원소를 앞에서부터 for문을 활용해 차례로 확인한다.
2. 만약 answer이 비어있거나 제일 마지막 값이 현재 확인하는 원소보다 작다면, 
     answer 맨 뒤에 넣어준다.
3. 그렇지 않다면 lower_bound를 사용해 answer에서 현재의 원소보다 큰 수들 중
   가장 작은 값을 가진 인덱스를 받아 온 뒤 그 인덱스의 값을 현재 원소로 바꾼다.
4. 모든 원소를 반복하면 answer는 가장 긴 증가하는 부분 수열이 된다.

위의 방법이 이 문제를 푸는 방법이다. 아래 코드를 보고 그림을 그려보거나하면 쉽게 이해를 할 수 있을 겁니다.

코드

# 12015번 가장 긴 증가하는 부분 수열 2
import sys

# lower_bound
def lower_bound(arr, start, end, n):
    while start < end:
        mid = (start + end) // 2

        if arr[mid] < n:
            start = mid + 1
        else:
            end = mid
    return end    

# main
n = int(input())
a = [int(x) for x in sys.stdin.readline().split()]

answer = []
for num in a:
    if len(answer) == 0:
        answer.append(num)

    if answer[-1] < num:
        answer.append(num)
    else:
        idx = lower_bound(answer,0,len(answer)-1,num)
        answer[idx] = num

print(len(answer))