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

문제 링크

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

12015번: 가장 긴 증가하는 부분 수열 2

 

풀이

- 최장 증가 수열(LIS) 문제

: 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중,

각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열 

https://zzion2.tistory.com/81

[백준 11053번] 가장 긴 증가하는 부분 수열 - python

위 문제에서는 dp로 풀었었는데 시간복잡도가 O(N^2)이다.

해당 문제는 범위가 1,000,000이기 때문에 시간 초과 발생 

이진 탐색을 사용한 lower bound 알고리즘으로 풀이해야 했다. 

 

- lower bound

: 원하는 값 k 이상이 처음 나오는 위치를 찾는 알고리즘 

: 시간 복잡도 O(NlogN)

# lower bound 
# num과 같거나 큰 가장 작은 인덱스 구하기 
def binary_search(arr, num):
    start = 0 
    end = len(arr) -1 
    
    while start <= end :
        mid = (start+end) // 2
        
        if arr[mid] >= num :
            end = mid -1 
        else:
            start = mid + 1 
    
    return start 
    
n = int(input())
data = list(map(int,input().split()))

max_list = []

for num in data:
    idx = binary_search(max_list, num)
    
    # 리스트의 최댓값보다 크므로 추가 
    if idx == len(max_list):
        max_list.append(num)
    # 해당 인덱스의 값을 업데이트 
    else:
        max_list[idx] = num
        
print(len(max_list))