✔ 풀이를 위한 아이디어
- 다이나믹 프로그래밍 (Dynamic Programming)
✔ 백준 11053번: 가장 긴 증가하는 부분 수열 (수정 전 코드) [메모리 초과]
import sys
from collections import deque
n = int(input())
nums = list(map(int, sys.stdin.readline().split()))
queue = deque([(nums[0], 0)])
ans = 0
while queue:
tmp = queue.popleft()
current_index = tmp[1]
current_num = tmp[0]
count = 1
for i in range(len(nums) - tmp[1] - 1):
if nums[current_index+1] > current_num:
count += 1
current_num = nums[current_index+1]
else:
queue.append((nums[current_index+1], current_index+1))
current_index += 1
if count > ans:
ans = count
print(ans)- '가장 긴 바이토닉 부분 수열' 문제를 풀기 전에, 그 전 단계 문제라고 할 수 있는 '가장 긴 증가하는 부분 수열' 문제를 풀어보았다.
- 처음 내가 짰던 방식은, 쭉 증가하다가 감소하는 순간의 숫자를 큐 (Queue) 에 넣어두고, 해당 숫자부터 다시 탐색하도록 하는 것이었다. 그러나 이 방식은 해당 숫자의 index까지도 기억해야하기 때문에 메모리 초과가 나게 되었다.
- 또한 이미 큐에 들어 있다고 하더라도, 탐색 과정에서 계속해서 넣게 되므로 시간초과도 발생했을 것으로 예상된다.
- 이 방법의 가장 큰 문제점은 '앞쪽'부터 조금씩 범위를 넓혀 탐색해가는 DP의 방식을 택하지 않고, '뒤쪽'에 있는 모든 경우를 탐색해 나갔다는 점이다.
✔ 백준 11053번: 가장 긴 증가하는 부분 수열 (수정 후 코드)
import sys
n = int(input())
nums = list(map(int, sys.stdin.readline().split()))
dp = [0]*n
for i in range(n):
for j in range(i): # 자신보다 '앞쪽'에 있는 수들에 대해서 탐색
if nums[i] > nums[j] and dp[i] < dp[j]: # 만약 증가하였는데, 더 좋은걸 들고 있으면?
dp[i] = dp[j] # 내 dp에 넣기!
dp[i] += 1 # 내가 추가됐으므로 항상 1씩 더해주기 / 최초라면 1만 더해줘서 dp 1로 만들기
print(max(dp))- 생각보다 떠올리기 어려운 알고리즘이다. 다음에 꼭 복습하도록 하자.
- 이 방법을 떠올리기 위해서는, 위에서도 언급했듯이 '앞쪽'부터 범위를 넓혀나가는 방식을 고민해야한다.
✔ 백준 11054번: 가장 긴 바이토닉 부분 수열
import sys
n = int(input())
nums = list(map(int, sys.stdin.readline().split()))
reversed_nums = nums[::-1] # 리스트 확장 슬라이싱으로 뒤집기
dp = [0]*n
r_dp = [0]*n
ans = [-1]*n
for i in range(n):
for j in range(i):
if nums[i] > nums[j] and dp[i] < dp[j]:
dp[i] = dp[j]
if reversed_nums[i] > reversed_nums[j] and r_dp[i] < r_dp[j]:
r_dp[i] = r_dp[j]
dp[i] += 1
r_dp[i] += 1
for i in range(n):
ans[i] = dp[i] + r_dp[n-i-1] # 겹치게 구하지 않으면, 1 1 과 같은 예제에서 오답이 된다.
print(max(ans)-1)- '바이토닉 부분 수열'이란 증가하다가 감소하는 수열을 의미한다. 이를 풀기 위해서 감소하는 부분수열을 구하는 dp를 구현해야 한다는 점을 캐치하였다.
- 처음에는, for문 안의 if문에서 부등호의 방향만을 바꾸는 방식을 택했었다. 그러나 이 방식은 감소하는 부분 수열에서 '마지막 지점', 즉 '가장 작은 지점'에 최대의 dp 값이 들어가게 된다.
우리가 원하는 '바이토닉 부분 수열'을 구하기 위해서는 증가하는 부분 수열의 '마지막 지점'과 감소하는 부분 수열의 '시작 지점'에 최대의 dp값이 들어가도록 구현해야 한다. - 이를 위해서 start라는 배열을 만들어서 '시작 지점'과 '마지막 지점'을 어떻게 이어보려고 노력했지만 결국 실패하였다.
- 정답은 리스트를 거꾸로 뒤집은 다음 여기에서 증가하는 부분 수열을 구하는 것이었다. 그러면 위에서 말했던 대로 감소하는 부분 수열 (뒤집은 리스트에서 증가하는 부분 수열)의 '시작 지점' (뒤집은 리스트에서는 '마지막 지점'에 해당한다)에 dp 값이 들어가게 된다.
코로나 2차 백신 맞고 회복한다는 핑계로 너무 오래 쉰 것 같다. 앞으로도 꾸준히 풀자!
✔ 관련 개념
- 다이나믹 프로그래밍 (Dynamic Programming)
