[알고리즘] 백준 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

문제를 보고 시간 초과가 날것을 알았지만, DFS로 구현이 가능할 것 같아 시도해보았다. 아래 코드는 DFS로 시간초과를 받은 코드이다.

실패코드

import sys

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

max = -sys.maxsize
def dfs(index):
    global max

    if len(temps) > max:
        max = len(temps)

    for i in range(index, len(numbers)):
        if not visited[i] and temps[-1] < numbers[i]:
            temps.append(numbers[i])
            visited[i] = True
            dfs(i)
            visited[i] = False
            temps.pop()

visited = [False for _ in range(N)]
for i in range(len(numbers)):
    temps = []
    if not visited[i]:
        temps.append(numbers[i])
        visited[i] = True
        dfs(i)
        visited[i] = False

print(max)

정답은 잘 나오지만, 이 코드의 전체 시간 복잡도는 O(N^2 * 2^N)이 된다.. N^2도 아니고 거기에 지수복잡도를 곱한 시간복잡도라니.. 당연히 시간내에 통과할리가 만무하다.

N이 최대 1000일때 시간 초과를 받지 않고 통과시키기 위해서는, 완전 탐색이 아닌 다른 두 방법으로 해결해볼 수 있다.
첫번째 방법은 DP를 이용한 풀이이다.

성공 코드(DP)

import sys

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
dp = [1 for _ in range(N)]

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

dp라는 리스트는 각 인덱스의 숫자가 끝에 올 경우 가질 수 있는 부분 수열의 최대 길이를 저장하게 된다. 그리고 이전 위치에서부터 현재 위치까지의 부분 수열 중에서, 현재 위치보다 작은 숫자를 가진 숫자들을 찾아 그 중에서 가장 긴 부분 수열의 길이에 1을 더한(현재 값이 더 크므로 수열에 새롭게 한 개의 숫자가 추가 되는 것이므로) 값을 dp[i]에 새롭게 갱신해준다.

최종적으로 답은 이 dp 리스트에서 가장 큰 value가 최장 부분 수열의 길이가 된다. 이 경우 시간 복잡도는 O(N^2)이 되므로 N이 1000일때 1000 * 1000 으로 문제에서 주어진 1초 내에 통과할 수 있게 된다.

그러나 이 코드는 만약 N이 1000이 아닌 10000 이상이 될 경우, 1초 라는 시간 내에 통과할 수 없다. DP보다 시간 복잡도를 더 줄이기 위해서는 이분 탐색을 이용해야한다.

성공 코드(binary search)

import bisect
import sys

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
dp = [numbers[0]] # 증가하는 부분 수열을 저장하는 리스트


for i in range(N):
    if numbers[i] > dp[-1]: # 리스트의 최대 값 보다 현재 값이 클 경우 리스트에 추가
        dp.append(numbers[i])
    else:
    	# 리스트의 최대 값 보다 현재 값이 작을 경우, 현재 숫자보다 크거나 같은 숫자 중에서 가장 작은 위치(왼쪽)을 찾아 해당 값의 위치를 현재 값으로 갱신한다.
        index = bisect.bisect_left(dp, numbers[i]) 
        dp[index] = numbers[i]

print(len(dp))

이분 탐색의 경우 리스트의 크기가 N이므로, 리스트 탐색에 O(logN)이 소모되고, 이를 N번 반복하므로 O(NlogN)으로 입력 크기가 더 증가하더라도 충분히 통과할 수 있게 된다.

아래 사진에서, 아래는 DP로 제출된 시간이고 위는 이진 탐색으로 제출된 시간이다. 약 4배가량 차이가 나는 것을 확인할 수 있다.