(백준 알고리즘 문제풀이) 12015번 가장 긴 증가하는 부분 수열 2

문제

문제 링크

 

문제 접근

• 백준 11055번  과 다른 점은 N의 range이다. 이점을 잘 생각해야 한다. 1,000 -> 1,000,000
• 시간복잡도 O(N logN)인 binary search를 사용해야 한다.

코드

시간 초과 코드 (시간 복잡도: O(N^2))

import sys

N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))

dp = [1] * N
for i in range(N):
    for j in range(i):
        if seq[i] > seq[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(dp)

 

통과 코드 ( 시간복잡도: O(NlogN)

import sys

N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))

dp = [0]
for i in range(N):
    start = 0
    end = len(dp) - 1

    while start <= end:
        mid = (start + end) // 2
        if dp[mid] < seq[i]:
            start = mid + 1
        else:
            end = mid - 1

    if start >= len(dp):
        dp.append(seq[i])
    else:
        dp[start] = seq[i]

print(len(dp)-1)

 

Binary search 개념 정리글이 있어서 공유합니다.

만족님 블로그

느낀점

시간 복잡도에 대한 개념에 대하여 이해할 수 있는 문제였다. 이전의 가장 긴 증가하는 수열과 같은 문제인 것 같은데 정의역의 범위가 늘었기 때문에 시간초과에 대한 문제에 대하여 생각하여야한다는 것이었다. 그리고 python3보다는 pypy3가 더 빠르다는 것 또한 알게되었다.