[백준 11053, 12015] 가장 긴 증가하는 부분 수열 1, 2

 

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

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

• 문제 설명

첫 번째 입력으로 수열의 길이를 입력받고 두 번째 줄에 수열을 입력받는다. 출력으로는 증가하는 부분 수열 중에 가장 긴 길이를 출력하면 된다.

 

이 문제 유형의 알고리즘으로는 LIS(Longest Increasing Subsequence)이다. 이 알고리즘에 대해서는 이진 탐색을 공부하면서 처음 알게 되었으며 이 유형의 문제를 푸는 데에 있어서 크게 두 가지 방법이 있다.

1. Dynamic Programming
2. 이진 탐색

---

Dynamic Programming

N = int(input())
A = [*map(int,input().split())]

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

 

먼저 dp리스트를 1로 초기화해준다. 그 후 리스트에서 현재 위치(i) 보다 이전에 있는 원소(j)가 작은지 확인한다. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면 된다. 

 

예를 들어 i = 4일때를 확인해 보자.

i = 4 j = 0 dp[4] =1

arr [4] > arr [0] true 이므로 dp [4] = max(dp [4], dp [0] + 1) 2이다.

i = 4 j = 1 dp[4] = 2

arr [4] > arr [1] false

i = 4 j = 2 dp[4] = 2

arr [4] > arr [2] true이므로 dp [4] = max(dp [4], dp [2] + 1) 2이다.

i = 4 j = 3 dp[4] = 2

arr [4] > arr [3] false

 

dp리스트를 표로 나타내면 다음과 같다.

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

 

LIS문제를 dp를 이용하여 풀게 되면 O(N^2)의 시간 복잡도를 가진다. 만약 시간을 줄이고 싶다면 이진 탐색으로 풀면 된다.

 

이진 탐색

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

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

from bisect import bisect_left
N = int(input())
A = [*map(int,input().split())]

dp = [A[0]]
for i in range(N):
    if dp[-1] < A[i]:
        dp.append(A[i])
    else:
        index = bisect_left(dp,A[i])
        dp[index] = A[i]
print(len(dp))

 

이진 탐색 알고리즘에서 배운 bisect_left를 이용하는 방법이다. 처음 dp리스트에 수열의 첫 번째 원소의 값을 저장하고 for문으로 수열을 돌면서 만약 dp리스트의 마지막 값보다 큰 값이면 그냥 dp리스트에 추가해 주고 만약 작거나 같으면 dp리스트에서 해당 값이 들어갈 자리를 bisect_left로 찾아서 dp의 값을 바꾸면 된다. 그러면 최종 dp에는 증가하는 수열만 남게 되고 이의 길이를 출력하면 된다. 이때 시간 복잡도는 O(NlogN)으로 dp보다 훨씬 빠르다.