백준 14003번: 가장 긴 증가하는 부분 수열 5 (Binary Search)

이 문제는 기존에 DP를 사용하여 LIS를 얻어내던 것들 더 빠른 시간 내에 구해야 하는 문제이다. 기존의 LIS를 구하는 방법은 수열의 길이 만큼의 DP리스트를 만들고, 인덱스 0부터 N-1까지 i번째 숫자를 탐색해 나간다. DP를 이용한 LIS풀이도 처음에 애를 먹었던 기억이 있기에 이전의 코드를 보고 다시 생각해 보았다.

DP 이용 N^2 (시간초과)

N=int(input())
lst=list(map(int,input().split()))
lis=[0 for _ in range(N)]
lis[0]=1
if N>=2:
    for i in range(1,N):
        minTrue=1   #lst[i]의 값이 그 전값들중 최소인지 아닌지 판별
        maxlis=0    #minTrue가 0일때, lis[i]는 이전 lis들중 최대값+1 판별
        for j in range(i):
            if lst[i]>lst[j]:
                minTrue=0
                if lis[j]>maxlis:
                    maxlis=lis[j]
        if minTrue==0:
            lis[i]=maxlis+1
        elif minTrue==1:
            lis[i]=1
          
print(max(lis))

 

기본적으로 dp리스트의 lis[k]는 lst[k]의 숫자가 LIS의 마지막 번호일 때의 최대 LIS 길이를 저장하고 있다.

먼저 0번째 인덱스는 항상 lis이므로 1을 할당한다. 다음부터 i번째 숫자를 탐색하는 과정에서 i이전의 0부터 i-1까지의 j번째의 숫자를 탐색한다. 만약 lst[j] 숫자가 lst[i]보다 작다면 lst[j]를 마지막으로 하는 LIS 뒤에 lst[i] 숫자를 붙일 수 있다는 뜻이다. 그 말은 dp리스트에서  lis[i]=lis[j]+1이란 뜻이다. j번째 숫자가 i보다 작은 경우의 최대 lis[j]값을 찾아 (maxlis) 1을 더해주어 lis[i]에 할당해 준다. 만약 j를 탐색하는 과정에서 lst[i]보다 작은 값이 하나도 없을 수 있다. 그렇다면 lst[i] 숫자를 뒤에 붙일 수 있는 LIS가 존재하지 않는다는 뜻이기에 lis[i]는 새로운 LIS를 시작하는 경우가 되므로 길이가 1이 된다. 이렇게 하면 시간복잡도가 N^2인 LIS를 구할 수 있다.

 

이분 탐색 이용 N*logN (정답)

import sys
from collections import deque

N=int(sys.stdin.readline().rstrip())
series=list(map(int,sys.stdin.readline().rstrip().split()))
lis=[series[0]]
lisind=[[] for _ in range(N)]
lisind[0].append(0)

def binary(start,end,val):
    if start==end:
        return start
    mid=(start+end)//2
    if lis[mid]==val:
        return mid
    elif lis[mid]<val:
        return binary(mid+1,end,val)
    else:
        return binary(start,mid,val)
        
for i in range(1,N):
    if series[i]>lis[-1]:
        lis.append(series[i])
        lisind[len(lis)-1].append(i)
    else:
        replaceind=binary(0,len(lis)-1,series[i])
        lis[replaceind]=series[i]
        lisind[replaceind].append(i)

print(len(lis))
ans=deque()
index=9999999
for i in range(len(lis)-1,-1,-1):
    if lisind[i]:
        for j in range(len(lisind[i])-1,-1,-1):
            if lisind[i][j]<index:
                ans.appendleft(series[lisind[i][j]])
                index=lisind[i][j]
                break

for i in ans:
    print(i,end=' ')

그렇지만 이분 탐색을 통해서 시간 복잡도가 N*logN 인 LIS를 구할 수 있다. 수열의 인덱스 0부터 N-1까지 탐색 할 때, 먼저 0번쨰 숫자가 담긴 lis 리스트를 만들어 준다. 그리고 i번쨰 다음 숫자 series[i] 탐색해 가며 만약 더 큰 수라면 lis 리스트 뒤에 더해주고, 만약 더 작은 수 라면 기존 lis 리스트에서 이분 탐색으로 series[i]보다 작은 최대 숫자 다음 숫자를 series[i]로 대체시켜 준다. 만약 series[i]가 기존 lis의 마지막 인덱스를 대체한다면 그 뒤 탐색 하는 숫자가 LIS 맨 뒤에 이어 붙을 수 있는 범위를 더 넓혀 준다. 그러므로 최대 길이의 LIS의 길이를 구하는 데에는 문제가 없다. 하지만 저장된 lis 리스트트 실제 최대 길이의 LIS가 아니다. 만약 series[N-1], 즉 마지막 값이 가장 작은 값이 된다면 lis 리스트에 맨 앞 숫자를 series[N-1]가 대체하게 된다. 그러나 실제 최대 길이의 LIS의 맨 앞 숫자는 series[N-1]가 아닐 것이다.

 

내가 문제를 해결한 방식은 i번째 series[i] 가 lis 리스트 값을 대체할 때마다 그 인덱스 i를 그 lis가 들어가는 위치에 lisind[]를 만들어저장해 주는 방법을 사용했다. 그렇게 하면 lis의 길이가 3이라면 lisind[0], lisind[1], lisind[2]에 각 lis 위치에 지금까지 가능했던 인덱스들이 저장되게 된다. 그렇다면 마지막 위치, 즉 lisind[2]의 값들은 실제 최장 LIS의 마지막 인덱스와 일치하게 된다. 만약 lisind[2]의 값들이 여러개 있다면 어떤것을 사용해도 상관 없다. 왜냐하면 작은 값을 사용하더라도 충분히 최장 LIS수열의 길이를 만들 수 있었다는 뜻이기 때문이다. 그렇지만 나는 최대한 이전 가능한 인덱스들의 범위를 넓히기 위해 최대값을 사용했다. lisind[2]의 최대값을 index에 저장하고, 순서대로 뒤에서부터 위치의 인덱스들을 탐색한다. lstind[1]의 리스트 중 실제 최장 LIS가 가능한 인덱스는 아까 저장한 index보다 작아야 하므로 작은 값들 중 최대값을 다시 index에 저장한다. 이를 0까지 계속하면 실제 최장 LIS의 인덱스들이 뒤에서부터 얻게 되어 ans에 appendleft 한다면 ans에는 실제 LIS의 series 인덱스들이 남게 된다.