[BOJ/백준] 12015번 가장 긴 증가하는 부분 수열 2 (LIS) (Python 파이썬)

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	28835	11762	8205	42.250%

 

문제

수열 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

 

---

LIS 유형의 문제입니다. 이전에 풀이했던 11053번과 매우 유사한 문제이지만, 해당 문제를 DP 알고리즘으로 풀이했을 때의 시간 복잡도가 O(N^2)이므로 시간 내에 풀이가 불가능합니다. 

https://great-park.tistory.com/28

[BOJ/백준] 11053번 가장 긴 증가하는 부분 수열 (LIS) (Python 파이썬)

따라서, 위 포스팅에서 언급했듯이 이번에는 좀 더 효율적인 binary search를 사용하여 풀이를 진행하겠습니다.

풀이

이분탐색을 활용한 LIS

부분 수열을 저장할 리스트를 생성하여, 항상 증가하는 형태를 유지하도록 값을 추가합니다. 이때 LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분탐색으로 탐색해서 넣어야 합니다. 
이분탐색은 일반적으로 시간복잡도가 O(logn)으로 알려져 있으므로, 위의 문제를 O(nlogn)의 시간복잡도로 해결할 수 있게 됩니다!

from sys import stdin
input = stdin.readline
N = int(input())
num = list(map(int, input().split()))
memorization = [0]

for x in num:
    #증가하는 것만 저장됨
    if memorization[-1] < x:
        memorization.append(x)
    else:
    #중간에 값을 넣아햐 하는 경우
        start = 0
        end = len(memorization)

        while start < end:
            mid = (start+end)//2

            if memorization[mid] < x:
                start = mid + 1
            else:
                end = mid
        memorization[end] = x
print(len(memorization)-1)

 

참고로, 위와 같이 이진 탐색을 직접 구현하지 않아도, bisect_left 이라는 함수를 불러와서 사용하면 실제로 더 빠른 시간 내에 해당 값의 위치를 알아낼 수 있습니다.

from bisect import bisect_left
x = bisect_left(list, value)