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

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

dp = [0]*N

for i in range(N):
    maxDp = 0
    for j in range(i):
        if nums[j] < nums[i]:
            maxDp = max(maxDp, dp[j])
    dp[i] = maxDp+1

print(max(dp))

우선 일반적인 풀이이다.

 

i에 대한 for문의 각각 수행하는 것은 다음과 같다.

0~i-1 인덱스에서, nums가 nums[i]보다 작으면서 dp가 최대인 값(maxDp)를 찾고, 현재 dp에 maxDp+1을 넣어주는 것이다.

즉, 예시와 같은 경우 dp의 값은, [1, 2, 1, 3, 2, 4]가 된다.

 

이 경우 빅오는, O(N*2)가 된다.

 

다음은 더 효율적인 풀이이다.

import sys
input = sys.stdin.readline


def getMinBiggerIndex(left, right, value):
    while left <= right:
        mid = (left+right)//2

        if stack[mid] >= value:
            right = mid-1
        else:
            left = mid+1

    return left


N = int(input())
nums = list(map(int, input().split()))

stack = [nums[0]]

for i in range(1, N):
    if nums[i] > stack[-1]:
        stack.append(nums[i])
    else:
        maxLowerIndex = getMinBiggerIndex(0, len(stack)-1, nums[i])
        stack[maxLowerIndex] = nums[i]

print(len(stack))

이 경우 stack이 핵심이다.

for문을 돌면서 스택의 마지막 노드보다 큰 값이 올 경우에는 stack에 추가시킨다.

반면, 작거나 같은 값(가령, K라고 하자)이 올 경우, 여기가 중요한데, stack에서 K 이상이면서 가장 작은 인덱스를, Binary Search를 통해 가져와서, 해당 인덱스에 nums[i]를 삽입해준다.

 

이 풀이의 빅오는, O(NlogN)이 된다.