문제 유형에 따라 다르게 풀어야한다.
1) 길이를 구해라 → (1) dp풀이 O(N^2), (2) 이진탐색 O(NlogN)
(시간 복잡도만 봤을 때는 (2) 이진탐색 풀이만 알면 될것 같지만, 최장 증가 수열 자체를 구해야할때는 (1)을 응용해야하므로,
(1),(2)번 모두를 알고 있어야한다.
2) 최장 증가 수열을 구해라 → (1)dp풀이+while문
1. 최장 증가 수열의 [길이]를 구해라
1️⃣ dp풀이 O(N^2) - 보통 N=1000정도
N = 전체 수열 길이
arr = 주어진 배열
dp[i] = i번째까지 최장 증가 수열의 길이
N =6, arr = [10, 20, 10, 30, 20, 50] 라 할때, i에 따라 아래 결과로 나오게됨
i:0, dp:[1, 1, 1, 1, 1, 1]
i:1, dp:[1, 2, 1, 1, 1, 1]
i:2, dp:[1, 2, 1, 1, 1, 1]
i:3, dp:[1, 2, 1, 3, 1, 1]
i:4, dp:[1, 2, 1, 3, 2, 1]
i:5, dp:[1, 2, 1, 3, 2, 4]
dp[i]=max(dp[j]+1,dp[i]) 여기서 max인 이유는 j가 0부터 i까지를 다 보면서 비교하기때문에 max가 없으면 작은 값 중에서도 더 큰 작은수의 길이를 고려하지 못하기때문이다.
📌 전체 코드
N = int(input())
arr = list(map(int,input().split()))
dp = [1]*N
for i in range(N):
for j in range(i):
if arr[i]>arr[j]:
dp[i]=max(dp[j]+1,dp[i])
print(max(dp))
관련 문제: https://www.acmicpc.net/problem/11053
2️⃣ 이진탐색 O(NlogN) - 보통 N=1,000,000정도
N = 전체 수열 길이
arr = 주어진 배열
dp[i] = 최장증가부분수열 (순서보장X)
bisect_left를 쓰는 이유: dp[-1] 원소를 최대한 작은 값으로 만들어주는 효과가 있다. 이를 통해 최장 증가가 가능하게 한다.
그런데, bisect_left을 쓰면 순서가 보장이 안된다. 즉 dp[-1]뿐만아니라 찾게되는 인덱스값이 그 이전이 될 수 있다.
예를 들면,
N = 7
arr = [2, 5, 3, 1, 4, 7, 6] 라고 할 때,
i:1, dp:[2, 5]
i:2, dp:[2, 3] #dp[-1] 원소를 최대한 작은 값으로 만들어주는 효과
i:3, dp:[1, 3] #순서가 보장이 안된다.
i:4, dp:[1, 3, 4]
i:5, dp:[1, 3, 4, 7]
i:6, dp:[1, 3, 4, 6]
그래서 이진탐색 방법으로는 최장 증가 수열을 직접적으로 구할 수가 없어서 dp방식과 함께 구하게 되는것이다.
📌 전체 코드
from bisect import bisect_left
N = int(input())
arr = list(map(int,input().split()))
dp = [arr[0]]
for i in range(1,N):
if dp[-1]<arr[i]:
dp.append(arr[i])
else:
idx = bisect_left(dp,arr[i])
dp[idx]=arr[i]
print(len(dp))
관련 문제: https://www.acmicpc.net/problem/12015
2. [최장 증가 수열]을 구해라
N = 7
arr = [2, 5, 3, 1, 4, 7, 6] 빨간색 - 선택된 수
dp = [1, 2, 2, 1, 3, 4, 4] (dp 방식으로 구한 각 인덱스까지의 최장 증가 수열 길이)
아래 코드를 보면 알 수 있듯이 최장 증가 수열 길이(max_length)를 하나씩 줄이고 dp[max_idx]==max_length에 충족할때까지
max_idx를 줄여나가면서 역순으로 최장증가 수열을 찾는다.
while max_idx>=0:
if dp[max_idx]==max_length:
lis.append(arr[max_idx])
max_length-=1
max_idx-=1
역순으로 찾았으니까 마지막에는 lis[::-1] 이나 lis.reverse()를 해주는데
이때 출력 형식이 배열형식이 아니니까 unpack을 해주는 *을 사용해서 *lis[::-1]로 반환한다.
📌 전체 코드
N = int(input())
arr = list(map(int,input().split()))
dp = [1]*N
for i in range(N):
for j in range(i):
if arr[i]>arr[j]:
dp[i]=max(dp[j]+1,dp[i])
max_length=max(dp)
print(max_length)
max_idx=dp.index(max_length)
lis = []
while max_idx>=0:
if dp[max_idx]==max_length:
lis.append(arr[max_idx])
max_length-=1
max_idx-=1
print(*lis[::-1])