[Python] 백준 12015 - 가장 긴 증가하는 부분 수열 2

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

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

---

https://onn5.tistory.com/35

[Python] 백준 1965 - 상자넣기 (LIS 개념 정리)

여기에서 봤던 LIS 문제는 DP를 통해 시간복잡도 O(n^2)으로 풀 수 있었다.

하지만 이번 문제는 DP로만 풀면 시간초과가 난다. 이분탐색을 통해 풀어야하며 이때 시간복잡도는 O(nlogn)이다.

 

Ex)

x는 부분 수열을 저장해 놓는 배열이다.

처음에는 arr[0] 값이 x에 들어간다.

인덱스	0	1	2	3	4	5
array	5	2	1	4	3	5
x	5

 

 

이제 arr[1] 값을 살펴본다. x[-1]과 비교해서 arr[1]이 더 작으면 x에 들어갈 위치를 찾고 변경시킨다.

x[-1] = 5 > arr[1] = 2

	0	1	2	3	4	5
array	5	2	1	4	3	5
x	2

 

 

arr[2] 값을 살펴본다. x[-1]과 비교해서 arr[2]이 더 작으면 x에 들어갈 위치를 찾고 변경시킨다.

x[-1] = 2 > arr[2] = 1

인덱스	0	1	2	3	4	5
array	5	2	1	4	3	5
x	1

 

 

arr[3] 값을 살펴본다. x[-1]과 비교해서 arr[3]이 더 작으면  x에 들어갈 위치를 찾고 변경시킨다.

그러나 arr[3]값이 더 크다. 이런 경우에는 그냥 x에 arr[3] 값을 추가한다.

x[-1] = 1 > arr[3] = 4

x.append(arr[3]=4)

인덱스	0	1	2	3	4	5
array	5	2	1	4	3	5
x	1	4

 

 

arr[4] 값을 살펴본다. x[-1]과 비교해서 arr[4]이 더 작으면 x에 들어갈 위치를 찾고 변경시킨다.

x[-1] = 4 > arr[4] = 3

x[-1] = arr[4] = 3

인덱스	0	1	2	3	4	5
array	5	2	1	4	3	5
x	1	3

 

arr[5] 값을 살펴본다. x[-1]과 비교해서 arr[5]이 더 작으면  x에 들어갈 위치를 찾고 변경시킨다.

그러나 arr[5]값이 더 크다. 이런 경우에는 x에 arr[5] 값을 추가한다.

x[-1] = 3 > arr[5] = 5

x.append(arr[5]=5)

인덱스	0	1	2	3	4	5
array	5	2	1	4	3	5
x	1	3	5

 

x값을 변경시킬 때 이분탐색이 쓰이는 것이다.

이분탐색 라이브러리도 있지만 구현을 통해 풀어봤다.

n=int(input())
arr=list(map(int,input().split()))
LIS = [arr[0]]

def binarySearch(e):
    start = 0
    end = len(LIS) - 1
    
    while start <= end:
        mid = (start + end) // 2
        
        if LIS[mid] == e:
            return mid
        elif LIS[mid] < e:
            start = mid + 1
        else:
            end = mid - 1
            
    return start


for i in range(n):
    if arr[i] > LIS[-1]:
        LIS.append(arr[i])
    else:
        idx = binarySearch(arr[i])
        LIS[idx] = arr[i]

print(len(LIS))

이분탐색은 이전에 배우고 응용은 안해봤는데 이렇게 사용해보니 새로웠다.

 

 

참고

https://one10004.tistory.com/217