[백준 12015][Python] 가장 긴 증가하는 부분 수열

문제 바로가기

12015번: 가장 긴 증가하는 부분 수열 2

1. DP 풀이법

• 현재 num과 이전의 값들의 비교하는데, 이전 값보다 현재값이 크다면 그 dp배열의 현재 값과, dp배열의 이전 값 + 1 중 더 큰 값으로 갱신한다.

• dp의 최댓값이 답이다.

N = int(input())
number = [int(x) for x in input().split()]
dp = [1] * N
for i in range(N):
    for j in range(i):
        if number[j] < number[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

2. Binary Search 풀이법

• LIS라는 빈 리스트에 number의 첫번째 원소를 넣는다.

• LIS 리스트의 가장 마지막 원소와 number의 원소를 비교하는데, 이 때 number가 더 작다면 LIS의 마지막에 이 숫자를 append한다.

• 만약 더 작은 숫자라면 이분탐색을 통해 이 숫자가 LIS 배열에서 어느 자리에 들어가야 할지를 찾는다. -> Lower bound

• 이분탐색을 통해서는 LIS를 정렬된 상태로 유지하면서 이 숫자가 삽입될 수 있는 위치들 중 인덱스가 가장 작은 지점을 찾는다.

def findLow(num):
    l = 0
    h = len(LIS)-1
    ret = 1000000

    while l <= h:
        mid = (l + h)//2
        if LIS[mid] >= num:
            if ret > mid:
                ret = mid
            h = mid - 1
        else:
            l = mid + 1

    return ret


N = int(input())
number = [int(x) for x in input().split()]
LIS = [number[0]]

for i in range(1, N):
    if LIS[len(LIS)-1] < number[i]:
        LIS.append(number[i])
    else:
        LIS[findLow(number[i])] = number[i]

print(LIS)
print(len(LIS))

 

REVIEW

DP의 풀이방식은 숫자 개수(N)개를 보는데 그 숫자보다 앞에 있는 숫자들을 다 보기때문에(N-1, N-2, ...) 시간복잡도가 O(N^2)이다.

하지만 이분탐색의 풀이는 숫자 개수(N) * 이분탐색으로 숫자가 들어갈 자리 찾는 시간복잡도(logN) = O(NlogN)이기 때문에 시간이 훨씬 더 단축됐다.