똑같은 문제인데 난이도에 따라 조건이 다르다.
무작정 풀기보다 알고리즘 공부를 먼저 하고 푸는게 도움이 될 것 같아서 공부부터!
LIS를 구하는 방법은 2가지다.
- DP
- 시간복잡도 : O(N^2)
- 최장길이와 실제 LIS 수열을 모두 구할 수 있다.
- 이분탐색
- 시간복잡도 : O(NlogN)
- 해당 방식으로는 최장 길이만 구할 수 있다. 실제 LIS 수열을 구하기 위해서는 역추적 과정을 거쳐야한다.
💡 N
번째 수에서 끝나는 수열의 LIS = N
번째 수의 앞에 있는 모든 원소 중 N
번째수보다 작은 수에 대해 해당 원소에서 끝나는 LIS들 중 가장 긴 길이 + 1 💡
N
번째 수에서 끝나는 수열의 LIS의 초기값은 기본적으로 1(자기자신)이다.
N
번째 수의 앞에 있지만 N
번째 수보다 크거나 같다면 이는 LIS가 아니게 되므로 무시한다.
수열 = [1, 5, 4, 2, 3, 8]
(1) 1
에서 끝나는 수열 [1]
의 LIS의 길이
[1]
1
(2) 5
에서 끝나는 수열 [1,5]
의 LIS의 길이
[1,5]
2
(3) 4
에서 끝나는 수열 [1,5,4]
의 LIS의 길이
[1,4]
2
(4) 2
에서 끝나는 수열 [1,5,4,2]
의 LIS의 길이
[1,2]
2
(5) 3
에서 끝나는 수열 [1,5,4,2,3]
의 LIS의 길이
[1,2,3]
3
(6) 8
에서 끝나는 수열 [1,5,4,2,3,8]
의 LIS의 길이
[1,2,3,8]
4
따라서 수열 [1, 5, 4, 2, 3, 8]
의 LIS는 [1,2,3,8]
로, 길이는 4이다.
dp[i] = i번째 인덱스에서 끝나는 LIS의 길이 (초기값=1)
array = [1,5,4,2,3,8]
dp = [1 for _ in range(len(array))]
for i in range(1, len(array)):
for j in range(i): # array의 처음부터 i-1번째까지
if array[i] > array[j]: # 현재값이 클때만
dp[i] = max(dp[i], dp[j]+1) # 더 큰 값으로 갱신
print(max(dp)) # 4
이 방법은 간단하지만, 시간복잡도가 O(N^2)라 문제에 따라 시간초과가 날 수도 있다.
기존 수열에서 현재 원소를 임의의 배열로 넣을 때, LIS를 유지하기 위한 최적의 위치를 이분탐색을 사용해서 구한 다음, 이 임의의 배열의 길이가 최대 몇까지 갔는지를 구하는 방식이다.
'수열'의 현재 원소가 'LIS'로 들어가기 위한 위치는 이분탐색으로 구하는 것이 중요 포인트!
위치를 찾고 해당 위치에 추가하거나 갱신한다.
LIS가 최대 얼마까지 길어졌는지가 답이다.
from bisect import bisect_left
array = [1,5,4,2,3,8,6,7,9,3,4,5]
lis = [array[0]] # 첫번째 원소 넣고 시작
for i in range(len(array)):
if array[i] > lis[-1]: # lis의 마지막값보다 크다면 추가
lis.append(array[i])
else: # 그렇지 않다면 이분탐색으로 적절한 위치 찾기
idx = bisect_left(lis, array[i])
lis[idx] = array[i] # 갱신
print(len(lis)) # 6
bisect
라이브러리를 써서 간단하게 작성할 수 있다.
[Python] 백준 14003 - 가장 긴 증가하는 부분 수열 5
dp[i] = 주어진 수열의 i번째 값이 이분탐색 과정 중에 몇번째 인덱스에 들어갔는지 저장
dp
배열에 해당값이 LIS
의 몇번째 인덱스에 들어갔는지 저장한다.dp[i] = (LIS에서의 인덱스, 수열의 i번째 값)
len(LIS)-1
이 lastIdx
이고, 1씩 줄여가며 끝부터 거꾸로 값을 찾을 것이다.dp
배열도 N-1
부터 0
까지 거꾸로 돈다.dp[i][0] == lastIdx
이면 dp[i][1]
을 정답에 추가하고, lastIdx
를 1 줄인다.from bisect import bisect_left
N = int(input())
numbers = list(map(int, input().split()))
lis = [numbers[0]]
dp = [(0,numbers[0])]
# 이분탐색으로 LIS 길이 구하기
for i in range(1,N):
if numbers[i] > lis[-1]:
lis.append(numbers[i])
dp.append((len(lis)-1, numbers[i]))
else:
idx = bisect_left(lis, numbers[i])
lis[idx] = numbers[i]
dp.append((idx, numbers[i]))
# 역추적으로 실제 LIS 구하기
L = len(lis)
lastIdx = L - 1
answer = []
for i in range(N-1,-1,-1):
if dp[i][0] == lastIdx:
answer.append(dp[i][1])
lastIdx -= 1
print(L) # LIS 길이
for a in answer[::-1]:
print(a, end=' ') # 실제 LIS 수열 (거꾸로 출력)
print()