백준 12015번 파이썬 | 가장 긴 증가하는 부분 수열 2 (LIS , 이분 탐색)

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

풀이

이 문제는 바로 전 글을 참고하자. namhandong.tistory.com/134

백준 11053번, 1965번, 2565번 파이썬 | 가장 긴 증가하는 부분 수열 관련 문제 (LIS)

여기서 달라진 점은 N이 백만개라는 건데 기존의 방식은 O(N^2) 이기 때문에 시간초과가 난다.

따라서 바이너리 서치를 사용해서 해결해야 한다.

사실 이 문제를 해결할 때 여러 사이트를 참고해서 풀었는데 두가지 방식이 있다.

1. 바이너리 서치를 구현해서 푸는 방법

2. bisect 를 사용해서 푸는 방법이 있다.

 

이 문제를 풀때는 가장 긴 증가하는 부분 수열을 찾는 문제이지만 결국에는 길이만 구하면 되기 때문에 다음과 같은 방식을 사용할 수 있다.

비록 부분 수열을 모두 찾아내는 완벽한 정답은 아니지만 문제에서 요구하는 답은 구할 수 있다. 

---

방법 1

#방법 1
# 12015
# 가장 큰 증가 부분 수열2 LIS (+이진탐색)

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
dp = [0]

for i in range(n):
    low = 0
    high = len(dp) - 1
    while low <= high:
        mid = (low + high) // 2
        if dp[mid] < A[i]:
            low = mid + 1
        else:
            high = mid - 1
    if low >= len(dp):
        dp.append(A[i])
    else:
        dp[low] = A[i]

print(len(dp) - 1)

 

 

방법2 

여기서 bisect는 바이너리 서치를 사용하는 모듈로 bisect_left(array,value)를 하게되면 array에서 해당 value의 인덱스를 구하는데 왼쪽이 경계선이다. 

#방법 2
import sys
input = sys.stdin.readline
from bisect import bisect_left

n = int(input())
A = list(map(int, input().split()))
dp = [0]

for a in A:
    if dp[-1] < a:
        dp.append(a)
    else:
        dp[bisect_left(dp, a)] = a

print(len(dp) - 1)

 

아래 사이트를 참고해서 풀었다.

suri78.tistory.com/199

[백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python