[BinarySearch] 가장 긴 증가하는 부분 수열 2

hooongs.tistory.com/129

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

m.blog.naver.com/PostView.nhn?blogId=bestmaker0290&logNo=220820005454&proxyReferer=https:%2F%2Fwww.google.com%2F

알고리즘 기초 - Lower Bound & Upper Bound

Lower bound 의 개념이 나온다.

What is Lower bound?

Lower Bound와 Upper Bound는 일종의 이분 탐색에서 파생된 것으로,

이분 탐색이 '원하는 값 k를 찾는 과정' 이라면 Lower Bound는 '원하는 값 k 이상이 처음 나오는 위치를 찾는 과정' 이며, Upper Bound는 '원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 과정'이다.

 

import sys

# Lower Bound
def LowerBound(arr, start, end, n):
    while start < end: # this is differ from normal BinarySearch
        mid = (start + end) // 2

        if arr[mid] < n: # if found array is less than -> search right side
            start = mid + 1
        else: 
            end = mid
            # greater or equal to -> not -1 that normally do
            # make end position as equal to mid
            # since we need to find greater value than target not equal
    return end

n = int(input())
a = [int(x) for x in sys.stdin.readline().split()]

answer = []

for num in a:
    if len(answer) == 0:
        answer.append(num)
    
    if answer[-1] < num: # compare last element and current input
        answer.append(num) # only greater appended
    
    else: # if next input is less than or equal to, 
    	  # find lowerbound within answer and update that idx in answer array
        idx = LowerBound(answer, 0, len(answer)-1, num)
        answer[idx] = num

print(len(answer))

Binary Search를 사용함으로 써 복잡도를 NlogN으로 감소시켰다.