백준 부분수열 문제는 정말 많은데 대강 접근방법은 2가지인 것 같다.

1. 동적 프로그래밍(Dynamic Programming)
2. 이진탐색

동적 프로그래밍(DP) 문제

11053번,11055번 가장 긴 증가하는 부분수열

두 개다 같은 문제이다. 왜 그런지 모르겠는데 그냥 2개 풀어서 포인트 챙기자

완전탐색으로 '50보다 작은 숫자는 10,20,30이니까 최장 증가수열은 10,20,30,50! 길이가 4구나' 하고 코드를 작성하면 시간초과가 나온다. 따라서 DP를 사용해야 한다.

문제해답

자기 보다 작은 인덱스 범위를 검사하면서, 그 인덱스에 대응되는 a배열의 숫자값이 자기보다 작으면 해당 숫자를 최대값으로 가지는 부분증가수열의 길이+1을 하는데 최대길이를 유지하면서 가기위해 max(기존값, 부분증가수열의 길이 + 1) 방식이다.

import sys

n = int(input())
a = list(map(int, sys.stdin.readline().split()))
result = [1] * n


for i in range(len(a)):
  for j in range(i):
    if a[i] > a[j]:
      result[i] = max(result[i], result[j]+1)

print(max(result))

아래 그림처럼 파란색에 해당하는 result[i]값을 갱신하는 코드인 것이다.

14002번, 가장 긴 증가하는 부분수열4

이번에는 가장 긴 증가하는 부분수열의 길이와 내용을 함께 주는 것이다.
길이를 구할 때 썼던 배열의 최댓값이 곧 부분수열의 최대길이었는데, 이 값을 가지고 1씩 감소시켜서 부분수열의 원소를 역추적하는 것이다.

문제해답

#14002번

import sys

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

dp = [1] * N

for i in range(1, N):
   for j in range(i):
      if num[i] > num[j]:
         dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))
order = max(dp)
arr = []
for i in range(N - 1, -1, -1): #역추적 시작
   if dp[i] == order:
      arr.append(num[i])
      order -= 1

arr.reverse()
for i in arr:
   print(i, end=' ')

이진탐색

12738번,12015번 가장 긴 증가하는 부분수열3

DP를 쓰는 문제와 입력과 출력형태, 요구사항이 똑같은 문제이다.
하지만 다른 점이 있다면 입력으로 받는 수열A의 크기N이 1000배 길다.
DP를 쓰는 문제는 1 <= N <= 1000이지만,
이번 문제는 1 <= N <= 1,000,000 이므로 똑같이 DP를 쓰면 시간초과가 난다.
12378번, 12015번 둘다 같은 조건에 정답 코드도 같은데 시간제한이 다르다. 12015번은 1초,512MB이고 12378번은 3초, 512MB이지만 둘다 LIS로 커버가능하다.

주어진 수열의 첫번째 요소를 넣고 나머지 요소와 순차적으로 비교하면서 더 크면 LIS배열에 추가하고, 아니면 적절한 인덱스 위치를 찾아내서 삽입하는 것이다.
인덱스를 찾는 방법이 이진탐색인 것이다.

#12015번
n = int(input())
A = list(map(int, input().split()))

LIS = [A[0]]

def findPlace(e):
   start = 0
   end = len(LIS) - 1

   while start <= end:
      mid = (start + end) // 2

      if LIS[mid] == e:
         return mid
      elif LIS[mid] < e:
         start = mid + 1
      else:
         end = mid - 1

   return start

for item in A:
   if LIS[-1] < item:
      LIS.append(item)
   else:
      idx = findPlace(item) # bisect_left(LIS, item)도 가능함.
      LIS[idx] = item

print(len(LIS))

14003번, 가장 긴 증가하는 부분수열5

DP를 사용했을 때도 길이가 아닌 부분수열 그 자체를 도출하려면 역추적으로 해서 원소를 모아야 한다.
이진탐색 + 역추적해서 증가수열 완성하기 버전인 것이다.

import sys

input = sys.stdin.readline

_ = input()
nums = list(map(int, input().split()))

def binary_search(lis_arr, num):  

   low = -1  # 접근 X
   high = len(lis_arr)  

   while low + 1 < high:
      # print(lis_arr)
      mid = (low + high) // 2

      if num > lis_arr[mid]: 
         low = mid
      else:
         high = mid

   return high


lis_arr = [-1000000001]
lis_total = [(-1000000001, 0)]  # number, index

nums = nums[::-1]  # stack처럼 쓰기 위해

while nums:
   num = nums.pop()

   if num > lis_arr[-1]:
      lis_total.append((num, len(lis_arr)))
      lis_arr.append(num)

   else:
      idx = binary_search(lis_arr, num)
      lis_arr[idx] = num
      lis_total.append((num, idx))
\lis_length = len(lis_arr) - 1
lis = []


while lis_total and lis_length: #역추적
   num, idx = lis_total.pop()
   if idx == lis_length:
      lis.append(num)
      lis_length -= 1

print(len(lis))
print(*lis[::-1])