최장 증가 부분 수열(LIS)에 해당하는 문제 시리즈이다.
입력과 출력, 시간 복잡도와 수의 범위에 따라 S2에서 P5까지 난이도가 준비되어 있다.
문제를 풀 당시에는 1 -> 4 -> 2 -> 3 -> 5 순으로 풀이했다.
LIS를 처음 접한다면 위 순서대로 푸는 것이 좋을 것이라 생각한다.
11053번 가장 긴 증가하는 부분 수열 / S2
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
입력되는 수열의 길이는 1000, 입력된 값은 모두 양수이다.
출력은 해당 수열의 길이만 출력하면 된다.
DP를 이용하여 풀이를 진행하였다.
i번째 값을 조사할 때 DP의 0번째 인덱스부터 확인하며, 더 작은 순간이 오면 해당 자리에 i번째 값을 넣는 방식으로 진행했다.
import sys
n = int(sys.stdin.readline())
subs = list(map(int, sys.stdin.readline().split()))
dp = [0]
for sub in subs:
if dp[-1] < sub:
dp.append(sub)
continue
for i in range(len(dp)):
if sub < dp[i]:
dp[i] = sub
break
elif sub == dp[i]:
break
print(len(dp)-1)인덱스 에러 방지를 위해 모든 수열의 값은 항상 1 이상이므로, 0을 미리 넣어 처리를 진행했다.
각 값에서 이미 저장된 모든 dp를 확인하고 있기 때문에 시간복잡도는 O(n^2)이다.
12015번 가장 긴 증가하는 부분 수열 2 / G2
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
입력되는 수열의 길이는 1,000,000, 입력된 값은 모두 양수이다.
해당 수열의 길이만 출력하면 되는 문제이다.
수열의 길이만 출력하면 되는 문제이지만, 입력된 수열의 크기가 굉장히 커졌다.
이전 풀이의 시간 복잡도인 O(n^2)로는 시간초과가 나게 되는 문제이다.
DP에 더불어, 이진 탐색을 추가했다.
import sys
n = int(sys.stdin.readline())
subs = list(map(int, sys.stdin.readline().split()))
dp = [0]
for sub in subs:
if dp[-1] < sub:
dp.append(sub)
continue
s, e = 0, len(dp)-1
mid = (s+e)//2
while s<e:
if e - s < 2:
mid = e if sub>dp[s] else s
break
if dp[mid] == sub:
break
if sub < dp[mid]:
e = mid
else:
s = mid
mid = (s+e)//2
if sub < dp[mid]:
dp[mid] = sub
print(len(dp)-1)
기존에는 dp의 인덱스를 0부터 시작해서 sub보다 더 작은 최초의 index를 구했다.
해당 인덱스를 구할 때 이진 탐색을 이용해서 찾는 방식으로 변경했다.
logN의 시간 복잡도 안에 원하는 값을 찾아내는 이진 탐색을 도입하여 시간초과를 피할 수 있었다.
N개의 데이터를 모두 이진 탐색해서 dp에 넣어야 하므로 시간 복잡도는 O(nlogn)이다.
12738번 가장 긴 증가하는 부분 수열 3 / G2
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
수열의 크기는 2번 문제와 동일하지만 입력되는 값의 범위가 매우 커졌다.
출력은 동일하게 해당 수열의 길이만 출력하면 되는 문제이다.
만일 타 언어였다면, 해당 값을 지원하기 위해 자료형을 변경할 필요가 있을 수 있으나, 파이썬의 경우 자료형을 자동으로 판별해 주기 때문에 이전 코드와 동일한 코드를 사용했다.
C++에서도 int의 경우 -2^31 ~ 2^31-1 (약 -21억 ~ 21억)까지 지원하므로 int를 사용한다면 문제가 없어 보인다.
import sys
n = int(sys.stdin.readline())
subs = list(map(int, sys.stdin.readline().split()))
dp = [-1000000001]
for sub in subs:
if dp[-1] < sub:
dp.append(sub)
continue
s, e = 0, len(dp)-1
mid = (s+e)//2
while s<e:
if e - s < 2:
mid = e if sub>dp[s] else s
break
if dp[mid] == sub:
break
if sub < dp[mid]:
e = mid
else:
s = mid
mid = (s+e)//2
if sub < dp[mid]:
dp[mid] = sub
print(len(dp)-1)입력 방식이 양수인 점을 이용해 dp에 0을 미리 넣었었는데, 해당 문제는 음수도 입력에 들어옴에 따라 dp의 기본 값을 변경했다.
14002번 가장 긴 증가하는 부분 수열 4 / G4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000 )
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러 가지인 경우 아무거나 출력한다.
1번 문제와 동일하게 여유로운 영역의 입력이 주어진다.
하지만 가장 긴 증가하는 부분 수열을 직접 구해야 한다는 점에서 조금 까다롭다.
기존에는 dp에 값을 담아 저장하였으나, dp에 인덱스를 담는 것으로 방향을 바꾸었다.
import sys
n = int(sys.stdin.readline())
subs = list(map(int, sys.stdin.readline().split()))
dp = [0] # index만 저장
dp_index = [-1] * n
for i in range(1, n):
if subs[dp[-1]] < subs[i]:
dp_index[i] = dp[-1]
dp.append(i)
continue
for j in range(len(dp)):
if subs[i] < subs[dp[j]]:
dp_index[i] = dp[j-1] if j-1 >= 0 else -1
dp[j] = i
break
elif subs[i] == subs[dp[j]]:
break
print(len(dp))
stk = []
i = dp[-1]
while i != -1:
stk.append(subs[i])
i = dp_index[i]
while stk:
print(stk.pop(), end=' ')
i번째 수열의 dp_index의 값이 -1이라면 i번째 수열이 포함된 증가하는 부분 수열의 제일 앞이 i번째 수열이라는 뜻이다.
하지만 이는 가장 긴 증가하는 부분 수열이라는 뜻은 아님에 주의해야 한다.
dp [-1]에는 가장 긴 증가하는 부분 수열의 index가 들어있으므로, 해당 인덱스가 가리키는 dp_index를 탐색하면 최종적인 가장 긴 증가하는 부분 수열을 구할 수 있다.
마지막 수열을 구할 때 dfs, stack, 재귀 등 여러 방법으로 구할 수 있으나, 즉각적으로 떠오른 방법인 stack으로 구했다.
시간 복잡도는 1번 코드와 동일한 O(n^2)이다.
14003번 가장 긴 증가하는 부분 수열 5 / P5
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.
입력 범위가 3번 문제와 같게 늘어났다
길이와 더불어 가장 긴 증가하는 부분 수열까지 출력해야 하는 문제이다.
앞선 문제에서 사용한 이진 탐색과, 인덱스로 수열 구하는 방식을 하나로 합쳤다.
시간 복잡도는 동일하게 O(nlogn)이다.
import sys
n = int(sys.stdin.readline())
subs = list(map(int, sys.stdin.readline().split()))
save_before_index = [-1] * n
dp=[0]
for i in range(1, n):
if subs[dp[-1]] < subs[i]:
save_before_index[i] = dp[-1]
dp.append(i)
continue
s, e = 0, len(dp)-1
mid = (s+e)//2
while s<e:
if e-s<2:
mid = e if subs[i] > subs[dp[s]] else s
break
if subs[i] < subs[dp[mid]]:
e = mid
else:
s = mid
mid = (s+e)//2
if subs[i] < subs[dp[mid]]:
save_before_index[i] = dp[mid-1] if mid-1 >= 0 else -1
dp[mid] = i
print(len(dp))
index = dp[-1]
stk = []
while index != -1:
stk.append(subs[index])
index = save_before_index[index]
while stk:
print(stk.pop(), end=' ')
dp_index라는 단어가 와닿지 않아서, 5번 문제에서는 save_before_index로 이름을 변경했다.
이분 탐색으로 구해진 인덱스인 mid를 이전 문제의 j로 치환하면 이해가 비교적 쉬웠다.
LIS 문제를 풀며 이진 탐색과 DP에 약하다는 것을 깨달았다.
해당 알고리즘으로 추가적으로 문제를 풀이할 예정이다.
'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| [임계경로/P5/Python3, C++] (0) | 2024.10.13 |
|---|---|
| [중량제한/G3/Python3] (0) | 2024.10.11 |
| [여행 계획 세우기/P2/Python3] (0) | 2024.10.10 |
| [Messi Gimossi/G4/Python3, C++] (0) | 2024.10.08 |
| [게임 개발/G3/Python3] (1) | 2024.10.07 |