11053 가장 긴 증가하는 부분 수열

유형 : dp

 

 LIS(Longest Increasing Subsequence)로 알려진 유명한 문제이다. 주어진 배열에서 몇 개의 요소들을 제거하여 만들 수 있는 가장 긴 증가하는 수열을 찾는 문제로, 배열이 [1,3,5,2,1,6] 으로 주어진 경우 [1,3,5,6]이 가장 긴 증가하는 부분 수열이 된다.

 

 아래의 풀이는 나무위키의 최장 증가 부분 수열을 Python으로 구현한 것이다.

 풀이를 살펴보면, 먼저 시간복잡도를 O(nlogn) 으로 하기 위해서는 이진탐색을 활용해야하므로, 먼저 이진탐색을 정의한다. bin_search 함수는 이진탐색으로 원하는 값보다 같거나 큰 가장 작은 수의 인덱스를 반환한다. dp[i]는 i+1번째 요소까지를 고려했을 때 가장 긴 부분 수열의 길이가 되며, p_i[i]는 길이가 i인 증가하는 부분수열의 마지막 수(가장 큰 수)이며, 이 값을 가장 작게 유지하는 것이 나중에 유리하다는 것을 알 수 있다.

 

풀이과정

1. bin_search를 통하여 p_i에서 a보다 크거나 같은 가장 작은 수의 인덱스를 찾는다(idx).

2-1. 이 idx가 배열 p_i의 길이와 같다면, 이는 가장 큰 수가 들어왔다는 것으로, 가장 긴 증가하는 부분 수열의 뒤에 붙으므로써 가장 긴 증가하는 부분 수열의 길이가 1 증가하게 된다. 즉, dp에는 idx 값을 넣어주고, p_i 에는 a 값을 추가로 넣어준다.(p_i의 길이가 늘어났다는 것은, dp의 최댓값 역시 늘어났다는 것을 의미한다.) 

2-2. idx가 배열 p_i의 길이보다 작다면, 이는 a 값을 마지막으로 하는 증가하는 부분 수열은 기존의 부분 수열보다 길이가 크지 않다는 것이고, idx는 a를 마지막으로 넣었을 때 만들수 있는 가장 긴 부분 수열의 길이를 나타낸다. 이 때, 기존의 길이가 idx인 부분 수열의 마지막 보다는 a가 작거나 같으므로 p_i[idx]의 값을 a로 바꾸어준다.

3. 이렇게 모든 요소에 대하여 반복한 후 dp의 최댓값을 반환한다.

 

시간복잡도

 1의 과정(이진탐색)의 시간 복잡도가 logn이고, 이 과정을 모든 요소에 대하여 반복해야 하므로 총 n번 진행하면 된다. 따라서 시간복잡도는 O(nlogn)이 된다.

 

코드

import sys

#t보다 크거나 같은 가장 작은 수 반환
def bin_search(arr, t):
    l=0
    r=len(arr)
    if t > arr[-1]:return len(arr)
    elif t<arr[0]:return 0
    mid = (l+r)//2
    while l<=r:
        if arr[mid] > t:
            r=mid-1
        elif arr[mid] < t:
            l = mid+1
        else:
            return mid
        mid = (l+r)//2
    return mid+1

n=map(int,sys.stdin.readline())
a_i = list(map(int,sys.stdin.readline().split()))

dp=[0]
p_i=[0]

for a in a_i:
    idx = bin_search(p_i,a)
    # 가장 큰 수가 들어왔다
    if idx == len(p_i):
        p_i.append(a)
    else:
        p_i[idx] = a
    dp.append(idx)
print(max(dp))

 

문제 풀기

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