[ BOJ 12015 ] 가장 긴 증가하는 부분 수열 2 (Python)

문제

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


[11053 가장 긴 증가하는 부분 수열] 이랑 동일한 풀이로 제출했다가 시간 초과가 났다. . . 🙂🙃🙂

dynamic programming 중 특별케이스인 lis에 대해 알 수 있었던 문제다.

문제 풀이

틀린 문제 풀이

먼저 dp로 접근해보려고 했다.

dp[i] = 배열의 i번째까지 만들 수 있는 가장 긴 수열의 길이

dp = [1] * n

for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[j]+1, dp[i])

print(max(dp))

근데 가차없이 시간 초과가 발생했다.
위의 코드는 O(N^2) 의 시간 복잡도를 가지는데,
이 문제는 숫자의 개수가 최대 1,000,000개이기 때문에 dp로는 풀 수 없다.

조금 더 서치를 해보다가 최장 증가 수열 LIS에 대해 알게 되었다.

이분 탐색으로 LIS 구하기

자손9319 님의 글을 보고 작성했습니다.
🔗 https://jason9319.tistory.com/113

O(N) 으로 수열을 처음부터 확인한 후, 최적의 자리를 찾기 위해 O(log N)가 소요된다.
결과적으로 O(N log N)의 시간 복잡도를 가지게 된다.

최적의 위치를 찾기 위해서 bisect 표준 라이브러리를 사용해주었다.

• bisect 라이브러리

import bisect import bisect_left

arr = [1, 2, 4, 5]
index = bisect_left(arr, 3)

arr.insert(index,3)

print(index)
# 2
print(arr)
# 1, 2, 3, 4, 5

• bisect_left, bisect_right 차이점

arr = [1, 2, 3, 3, 4, 5]
l_index = bisect_left(arr, 3)
r_index = bisect_right(arr, 3)

print(l_index, r_index)
# 2 4
# bisect_left : 가장 왼쪽에 위치한 요소 위치 반환
# bisect_right : 가장 오른쪽에 위치한 요소 위치 반환

1. lis 배열을 만들어준다.

2. 수를 입력받은 a의 배열의 각 요소에 대해, lis 배열의 맨 뒤 원소와 비교를 해줄 것이다.

2-1. a의 요소가 더 클 경우, lis에 append 해준 뒤 ans를 1 증가시킨다.

if lis[-1] < num:
   lis.append(num)
   ans += 1

2-2. a의 요소가 더 작을 경우, bisect로 lis의 최적의 자리를 찾은 뒤 그 자리의 값을 a 요소로 교체한다.

else:
   index = bisect_left(lis, num)
   lis[index] = num

3. 모든 a 배열에 대해 2-1, 2-2를 반복한다.

🔥 이때 중요한 점은 lis 배열에 들어있는 값들이 LIS(최장 증가 수열)은 아니라는 점이다.

수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색 된 최적의 위치가 앞에 있을 수도 있기 때문입니다.

출처: [ACM-ICPC 상 탈 사람]

코드

import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().rsplit()))
lis = []
ans = 0

for num in a:
    if not lis:
        lis.append(num)
        ans += 1
        continue
    
    if lis[-1] < num:
        lis.append(num)
        ans += 1
    else:
        index = bisect_left(lis, num)
        lis[index] = num
    # print(lis,num,ans)
    
print(ans)