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
에 대해 알게 되었다.
자손9319 님의 글을 보고 작성했습니다.
🔗 https://jason9319.tistory.com/113
O(N) 으로 수열을 처음부터 확인한 후, 최적의 자리를 찾기 위해 O(log N)가 소요된다.
결과적으로 O(N log N)의 시간 복잡도를 가지게 된다.
최적의 위치를 찾기 위해서 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
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 : 가장 오른쪽에 위치한 요소 위치 반환
lis
배열을 만들어준다.
수를 입력받은 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
a
배열에 대해 2-1, 2-2를 반복
한다.🔥 이때 중요한 점은 lis 배열에 들어있는 값들이 LIS(최장 증가 수열)은 아니라는 점이다.
수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색 된 최적의 위치가 앞에 있을 수도 있기 때문입니다.
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)