[Python] 백준 - 14002 가장 긴 증가하는 부분 수열 4

 

문제

수열 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 (다이나믹 프로그래밍)를 이용한 방법

 

1) 혼자서 떠올리기 어려운 만큼, 코드를 뜯어보며 이해하는 게 좋을 듯 하다.

이해하기가 어렵진 않다.

 

2. Binary Search (이진 탐색)을 이용한 방법

 

1) 이진 탐색 함수 부분에서 mid에 해당하는 값이 없을 경우, l을 출력해야한다.

 

- [10, 20] 의 리스트에서 이진탐색으로 찾는 k 가 15라면 20의 위치가 출력된다.

- [10, 20, 30, 40] 의 리스트에서 이진탐색으로 찾는 k 가 35라면 40의 위치가 출력된다.

 

2) 나머지는 코드를 보며 이해해보기를 추천한다. (혼자서 백지상태에서 떠올린다면 천재아닐까 싶다.;;)

 

 

DP

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
d = list(map(int, input().split()))
dp = [1 for _ in range(n)]
ans = []

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

idx = max(dp)
print(idx)
i = n-1
while True:
	if idx == 0:
		break
	if dp[i] == idx:
		ans.append(d[i])
		idx -= 1
	i -= 1
print(*ans[::-1])

 

 

 

Binary Search 이용

 

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
d = list(map(int, input().split()))
dp = [[0, 0] for _ in range(n)]
dp[0] = [1, d[0]]
res = [d[0]]
ans = []

def binary(arr, k):
	l, r = 0, len(arr)-1
	while l <= r:
		mid = (l+r)//2
		if arr[mid] == k:
			return mid
		elif arr[mid] > k:
			r = mid-1
		else:
			l = mid+1
	return l

for i in range(1, n):
	if res[-1] < d[i]:
		res.append(d[i])
		dp[i] = [len(res), d[i]]
	else:
		idx = binary(res, d[i])
		res[idx] = d[i]
		dp[i] = [idx+1, d[i]]
		
print(len(res))
rdx = len(res)
for i in range(n-1, -1, -1):
	if dp[i][0] == rdx:
		ans.append(dp[i][1])
		rdx -= 1
print(*ans[::-1])