[Python3]백준_가장 긴 증가하는 부분 수열

문제출처: https://www.acmicpc.net/problem/12015

접근법

처음에는 주어진 배열을 분할정복으로 결과값을 더해가는 방식을 생각했었다.
DP를 활용하여 이전값을 현재값에 더해가지만 분할정복 이후 왼쪽집합과 오른쪽집합과의 비교가 다시 필요하기 때문에 시간복잡도는 O(n^2)이 되어서 실패한 것 같다.

최장 증가 부분 수열(LIS) 알고리즘은 O(n^2)의 복잡도를 해결하기 위하여 이분탐색을 활용한다.

1. 현재까지의 최장 증가 부분 수열의 마지막 값보다 큰 값이 들어오면 수열의 끝에 추가한다.

2. 만약 마지막 값보다 작은 값이 들어온다면 현재 최장 증가 부분수열 안의 가장 비슷한 값을 현재값으로 대체한다.

• 대체하는 과정이 필요한 이유는 간단한 예시로 입력이
  2 3 4 5 1 2 3 4 5 일 경우
  현재값이 1일때 현재 수열은 [2,3,4,5]이므로 가장 비슷한 값인 2를 1로 대체함으로써 현재까지의 최적의 답을 유지할 수 있고 추후 현재값인 1부터 시작하는 더 긴 증가 부분 수열을 찾을 수 있게 된다.
  [1 3 4 5 ] 현재값 : 1
  [1 2 4 5 ] 현재값 : 2
  [1 2 3 5 ] 현재값: 3
  [1 2 3 4 ] 현재값: 4
  [1 2 3 4 5] 현재값: 5

출처:https://jainn.tistory.com/90

코드

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int,input().split()))

memoization = [0]

for number in numbers:
    if number > memoization[-1]:
        memoization.append(number)
    else:
        left,right = 0,len(memoization)
        while left < right:
            mid = (left+right)//2
            if memoization[mid] < number:
                left = mid+1
            else:
                right = mid
        memoization[right] = number

print( len(memoization)-1 )