백준 12015번: 가장 긴 증가하는 부분 수열 2 (Python)

접근

가장 긴 증가하는 수열은 동적계획법에서 나왔던 문제이고, 그때도 굉장히 오래 고민했던 기억이 난다.

2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

이번 문제는 그와 같은 문제이긴 하지만 입력되는 수열의 크기가 훨씬 커서 동적계획법으로는 시간안에 풀 수 없다...고 하여 이분탐색 알고리즘을 이용해야 하는데, 사실 스스로 풀지 못하고 풀이를 보고 코드를 짜게 되었다. 가장 긴 증가하는 부분 수열 알고리즘에 대해 아래 링크에서 도움을 많이 받았다. 링크에 아주 이해하기 쉽게 설명되어 있다.

최장 증가 부분 수열

최장 증가 부분 수열 - 나무위키

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
dp = [0]

for i in range(n):
    low = 0
    high = len(dp) - 1

    while low <= high:
        mid = (low + high) // 2
        if dp[mid] < a[i]:
            low = mid + 1
        else:
            high = mid - 1

    if low >= len(dp):
        dp.append(a[i])
    else:
        dp[low] = a[i]

print(len(dp) - 1)

더 생각해 볼 것?

이분탐색 알고리즘임을 알고있어도 이 문제는 어떻게 푸는지 전혀 감을 잡지 못했다. 다음번에 비슷한 문제를 만나더라도 헤메지 않도록 숙지해야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!