유형 : 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번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2839 설탕배달 (0) | 2020.02.24 |
|---|---|
| 백준 11052 카드 구매하기 (0) | 2020.02.24 |
| 백준 7576 토마토 (0) | 2020.02.21 |
| 백준 15998 카카오머니 (0) | 2020.02.20 |
| 백준 1931 회의실 배정 (0) | 2020.02.17 |
