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

💡문제접근

• 2중 for문을 통해서 가장 긴 증가하는 부분 수열을 구하는 문제가 아니라 이분 탐색으로 탐색의 범위를 좁히는 방법으로 작성해야한다. 이분 탐색은 정렬이 된 데이터에 대해서만 수행이 가능하다고 알고 있었는데 이걸 어떻게 적용해야할지 몰라서 막막하다가 최장 증가 부분 수열에 대한 포스팅을 보고 공부하며 어떤 로직으로 동작이 되는지 알 수 있었다.

최장 증가 부분 수열(LIS) 알고리즘

💡코드(메모리 : 155588KB, 시간 : 3704ms)

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().strip().split()))
dp = [1 for _ in range(N)]
memoization = [0]

for i in A:
    if memoization[-1] < i:
        memoization.append(i)
    else:
        left = 0
        right = len(memoization)
        while True:
            if left >= right:
                break
            mid = (left + right) // 2
            if memoization[mid] > i:
                left = mid + 1
            else:
                right = mid
        memoization[right] = i
print(len(memoization) - 1)

💡소요시간 : 1h