백준 12015번 가장 긴 증가하는 부분 수열2
<문제>
수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
해당 문제는 가장 긴 증가하는 부분 수열(11053번) 문제와 매우 유사하다. 입력되는 수열의 크기와 수열을 이루는 숫자의 크기만 다를 뿐이다.
크기가 상당히 커진게 보인다.
정답? 골드 2인데 한번에 가나?
어림없지! 바로 시간초과~
bisect를 이용한 이분 탐색
import bisect
n = int(input())
arr = list(map(int, input().split()))
dp = [arr[0]]
for i in range(1, n):
if arr[i] > dp[-1]:
dp.append(arr[i])
else:
dp[bisect.bisect_left(dp, arr[i])] = arr[i]
print(len(dp))LIS(Longest Increasing Subsequence) 알고리즘은 시간복잡도가 O(N^2)이기 때문에 길이가 10^6일 때 시간초과가 뜬다. 시간 복잡도를 개선하기 위해서는 이분 탐색을 활용해야한다. 그러면 시간복잡도가 O(nlogn)으로 개선된다.
입력 예제인 [10, 20, 10, 30, 25, 50]로 코드를 조금 뜯어서 살펴보자.
for i in range(1, n):
if arr[i] > dp[-1]:
dp.append(arr[i])
else:
dp[bisect.bisect_left(dp, arr[i])] = arr[i]
해당 반복문을 돌면서 dp는 아래와 같이 변화한다.
맨 처음 dp = [arr[0]]이므로 [10]이다.
i = 1 일 때에는 [10, 20]
i = 2 일 때에는 [10, 20] 여기서 첫번째 원소 10은 arr의 세번째 원소 10이다.
i = 3 일 때에는 [10, 20, 30]
i = 4 일 때에는 [10, 20, 25]
i = 5 일 때에는 [10, 20, 25, 50]
이렇게해서 dp의 길이를 출력해주면 그게 답이다.
이분탐색으로 값을 갈아끼워주는 이유는 무엇일까?
조금 더 이해하기 쉬운 배열 [10, 20, 50, 15, 30, 35] 로 설명해보겠다.
위와 같은 경우, 처음부터 끝까지 순차 탐색을 하면서 단순 크기 비교를 통해 LIS를 만들어 나간다면,
10을 담고 -> 10보다 큰 20을 담고 -> 20보다 큰 50을 담고, 이후에 50보다 큰 원소가 없으므로 [10, 20, 50]이 나온다.
하지만 실제 LIS는 길이가 4인 [10, 20, 30, 35]가 될 것이다.
50 다음에 15가 작다고 바로 제외하는 것이 아니라, 이전에 만들어 놓은 LIS에서 15 이상의 수(여기서는 20을 뜻한다.)를 15로 대체해주면, 이후 더 많은 수를 받아들일 수 있게 된다. 이렇게 되면 [10, 15, 50]이 되는데 15는 사실 50 앞에 올 수 없다. 이때 그냥 15를 20이 담겨있는 것으로 취급해도 무방하다. 15를 넣은 것은 길이 자체는 변하게 하지 않으면서 뒤에 남은 애들을 탐색할 수 있게 하기 위함니다.
여기서 주의 할 것은 이분탐색으로 구한 LIS와 실제 LIS의 값은 다르다는 것이다.
실제 LIS의 값은 [10, 20, 30, 35]이다.
하지만 이분탐색으로 구한 LIS는 [10, 15, 30, 35]이다.
참 말로 설명하기 어려운 개념인 것 같다.
