백준 12015 : 가장 긴 증가하는 부분 수열 2 (python)

본문 링크

📌 이분탐색 코드

import sys
input=sys.stdin.readline

N=int(input())
L=list(map(int,input().split()))

dp=[0]

for i in L:

    if dp[-1]<i:
        dp.append(i)
    else:
        start=0 ; end=len(dp)-1 # 이분탐색을 L 리스트가 아니라 이미 정렬된 DP 리스트에서 탐색한다.
        while start<=end:
            mid=(start+end)//2
            if dp[mid]<i:
                start=mid+1
            else:
                end=mid-1
        if start>=len(dp): #start값이 dp의 길이보다 크거나 같으면 그냥 붙인다.
            dp.append(i)
        else:
            dp[start]=i
print( len(dp)-1)

📌bisect 라이브러리 코드

from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))

dp=[ L[0] ]
answer=1

for i in L:

    if dp[-1]<i:
        dp.append(i)
        answer+=1
    else:
        index=bisect_left(dp,i)
        dp[index]=i

print(answer)

📌 어떻게 접근할 것인가?

이전의 가장 긴 증가하는 부분 수열 문제에서는 $O(N^2)$ 을 활용한 풀이방법을 사용했다.
하지만 이번에는 $N$ 의 범위가 $N (1 ≤ N ≤ 1,000,000)$ 이기때문에
$O(N^2)$ 알고리즘을 사용할수 없다.
따라서 이분탐색을 활용하여 $O(Nlog N)$ 알고리즘을 사용하고자 한다.

먼저 이분탐색 코드부터 살펴보자

📌 어떻게 이분탐색을 사용할 것인가?

이분탐색의 목적은 어떤 특정한 최대값&최소값을 찾는 것이며 , 그 전제조건은 리스트가 정렬되어있어야 한다는 점이다.

하지만 우리는 단순히 가장 긴 부분수열을 구하는것이 목적이지 최대값이나 최소값을 구할 필요가없으며
리스트 또한 정렬되어있지않다.

일단 입력받을 리스트와 $DP$ 테이블을 만들어 보자.

$L=[10 , 20 , 40 , 25 , 20 , 50 , 30 , 70 , 85 ]$

$dp=[10]$

현재 $dp$ 테이블에는 10 이 저장되어있다.
그리고 이제 값이 증가해주면 증가값을 그대로 $dp$ 에 저장해주자.

$dp=[10,20,40]$

하지만 이떄 25 로 값이 감소했을때 25 를 dp 배열중 넣을수있는 최적에 장소에 값을 삽입한다.

따라서 다음 $dp$ 값은

$dp=[10,20,25]$ 가 된다.

이때 우리는 $dp$ 를 항상 오름차순으로 정렬했기때문에 이분탐색이 가능하다.
즉 특정 값이 감소할때 그 값을 $dp$ 배열에 넣을때 최적의 장소를 이분탐색으로 값을 삽입한다.

따라서 $dp$ 배열의 변화는 아래와 같다.

$dp=[10,20,25,50]$ , $dp=[10,20,25,30]$ , $dp=[10,20,25,30,70]$ , $dp=[10,20,25,30,70,85]$

따라서 우리는 $LIS-Longest$ $Increasing$ $Subsequence$ 값이 6 이 됨을 확인할수 있다.

이제 코드를 보면 dp[-1]<i 일때 dp.append(i) 를 한다.
만약 그렇지 않을 경우 이분 탐색으로 최적의 장소를 찾아준다.

📌 bisect 라이브러리

파이썬에는 bisect 라이브러리를 제공한다.
이때 bisect_left 를 import 하고 사용했을때
bisect_left(#배열,#값) 이 가지는 의미는
배열에서 특정한 값보다 크거나 같은 최소 인덱스는 얼마인가? 를 해결해준다.

예를들면 $dp=[1,2,3,5]$ 가 있다고 하자.
이때 bisect_left(dp,4) 를 하면 5 가 들어있는 인덱스 값인 3 을 반환해준다.
즉 이분탐색 코드를 구현하지 않아도 알아서 최적의 장소를 찾아주기때문에 아주 유용한 라이브러리이다.

또한 bisect 는 실제 이분탐색을 구현한 코드보다 속도가 더 빠르니 가능하면 bisect 라이브러리를 사용하자.
따라서 우리는 $O(Nlog N)$ 으로 가장 긴 증가하는 부분수열의 길이를 구할수 있다.

하지만 우리가 이떄가지 구한 값은 가장 긴 증가하는 부분 수열의 길이 일뿐
가장 긴 증가하는 부분수열의 배열이 아니다.
따라서 $LIS$ 를 이분탐색으로 구현해서 $DP$ 배열을 만들어도
이 $DP$ 배열은 가장 긴 증가하는 부분수열의 길이를 위한 배열일 뿐이지
실제로 증가하는 배열을 모은 리스트가 아님을 주의하자.

✅ 코드에서 주의해야할 부분

• 이분탐색에서 start 값을 반환한다.
• 만약 start>=len(dp) 일때 dp.append(i) 를 해준다. 그렇지 않을경우 dp[start]=i 로 설정한다.
• bisect 라이브러리를 활용할때 인덱스 에러를 막기 위해 dp 초기값은 0 으로 설정한다.