문제
수열 A가 주어졌을 때, 가잔 긴 증가하는 부분수열을 구하는 문제이다.
풀이
본 문제는 LIS 알고리즘을 사용하여 풀었다.
또한, 본 문제를 풀기 위해 두 가지의 배열을 사용하였다.
lis_arr: 이분 탐색을 사용하기 위한 배열lis_total: LIS를 구하기 위해 사용한 배열
가령 [10, 20, 10, 30, 20, 50]가 입력값으로 주어졌다고 해보자.
처음 input인 10은 lis_arr.top인 -inf보다 크다. 그러므로 뒤에 붙여준다. lis_arr의 첫 번째 index에 들어갔기에 lis_total도 (10, 1) 꼴로 업데이트 해준다.
두 번째 input인 20은 lis_arr.top인 10보다 크다. 그러므로 뒤에 붙여준다. lis_arr의 두 번째 index에 들어갔기에 lis_total도 (20,2)로 업데이트 해준다.
세 번째 input인 10은 lis_arr.top인 20보다 작다. 따라서 binary search를 통해 lis_arr에 들어가기 적절한 위치를 찾아준다. 여기서 적절한 위치라 함은, lis_arr의 단조증가성을 유지해주는 위치를 의미한다. lis_arr[1]이 -inf보다는 크고 20보다는 작기 때문에 lis_arr[1]에 10을 넣고 lis_total도 업데이트 해준다.
네 번째 input인 30은 lis_arr.top인 20보다 크다. 따라서 뒤에 붙여주며 lis_arr의 3번째 index가 되기에 lis_total도 (30,3)으로 업데이트 해준다.
다섯 번째 input인 20은 lis_arr.top인 30보다 작다. 따라서 binary search를 통해 lis_arr의 적절한 위치에 삽입하고 lis_total도 수정해준다.
여섯 번째 input인 50은 lis_arr.top인 30보다 크다. 따라서 뒤에 삽입해주며 lis_total도 업데이트 해준다.
input에 대한 모든 작업을 다 하면 위와 같은 모습이 된다.
여기서 -inf를 제외한 lis_arr의 길이가 가장 긴 증가하는 부분수열의 길이가 된다. 여기서 주의할 점은 lis_arr은 현재 예시에서는 가장 긴 증가하는 부분수열처럼 보이지만, 이는 우연일 뿐, 실제로 lis_arr만으로는 가장 긴 증가하는 부분수열을 구할 수 없다. 이를 구하기 위해서는 lis_total을 사용해야 한다
lis_total을 뒤에서부터 읽어오면서 lis_total[i][1]가 1 감소할 때마다 해당 값을 저장하면 된다.
따라서 가장 긴 길이가 증가하는 부분수열은 [10,20,30,50]이 된다.
즉 알고리즘을 정리하자면 다음과 같다.
input값을 앞에서부터 읽어준다.input[i]을lis_arr의 맨 마지막 값과 비교해준다.
2.1. 만약input[i]가 더 크다면lis_arr맨 마지막에 append 해준다.
2.2. 만약input[i]가 더 작거나 같다면lis_arr내 적절한 위치에 삽입해준다.input[i]가lis_arr[j]에 들어갔다면lis_total에(input[i], j)를 append 해준다.
코드
import sys
input = sys.stdin.readline
_ = input()
nums = list(map(int, input().split()))
# Binary_search method
def binary_search(lis_arr, num): #
low = -1 # 접근 X
high = len(lis_arr) # 접근 X
# 결정 문제
# [1 3 5] 에서 2가 들어오면 [2 3 5]가 되어야 함
# num은 mid보다 큰가? -> TF문제에서 가장 작은 F (high)
# 왜 초과인가? -> 같은 숫자가 들어올 수 있기 때문
while low +1 < high:
#print(lis_arr)
mid = (low + high)//2
if num > lis_arr[mid]: # TTF므로 왼쪽 탐색 X
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 = []
#print(lis_total)
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])비고
맞았습니다!!를 볼 때까지 많은 틀렸습니다를 봐왔다. 그 중 두 가지 실패 사례에 대해 말하겠다.
비고 1. 이분 탐색 코드 오류
if num > lis_arr[mid]:를 if num >= lis_arr[mid]: 라고 잘못 썼었다. 만약 이렇게 잘못 쓴다면 이미 lis_arr에 숫자가 있을 경우를 고려하지 못한다.
만약 lis_arr이 [-inf, 10, 20]이고 새로운 숫자로 10이 들어온다고 해보자. 새로운 숫자 10은 lis_arr[1]인 10보다 크거나 "같기" 때문에 탐색을 한 번 더 하고 결국 [-inf, 10, 10]이 되어버린다.
비고 2. 범위 오류
문제를 제대로 읽지도 않고 배열 내 숫자의 범위가 자연수라고 단정해버렸다.
따라서
lis_arr = [-1000000001]
lis_total = [(-1000000001,0)]처럼 써야하는 구간을
lis_arr = [-1]
lis_total = [(-1,0)]으로 정의했다.
배열의 맨 처음에 왜 -1을 넣었냐면 이진분류 분제를 parametric search로 풀기 위함이었다. 따라서 해당 값은 절대로 접근해서는 안되는 부분이다. 그러나 새로운 숫자로 -54처럼 -1보다 작은 수가 들어오면 접근을 허용해버린다. 따라서 문제에서 제공한 최소값 -1로 수정해주었다.
