LIS 알고리즘 (최장 길이 증가수열)

DP로 푸는 방법과 O(nlogn)의 시간 복잡도로 푸는 방법이 있다.

(백준)DP로 푸는 LIS
1차원 배열을 만든 뒤, 현재 탐색하는 인덱스보다 아래에 있는 인덱스 중
현재 인덱스의 수보다 작은 수라면 그 수까지 카운트 된 수열의 길이에 1을 더한 값을 현재 값과 비교하여 갱신한다.

(백준)O(nlogn)의 시간 복잡도로 해결
그러나 DP로 푸는 방법은 N이 커지면 감당 불가하다.
그래서 이분 탐색을 사용한 풀이를 활용한다.

from bisect import bisect_left


A = [10, 20, 40, 30, 10, 50] # 원본 수열

sequence = [-1] # A에 들어갈 가능한 수보다 작은 수를 넣어서 초기화

for i in range(len(A)):
	if sequence[-1] < A[i]: # sequence의 마지막 값보다 크면
    	sequence.append(A[i]) # 그대로 추가
    else:
    	idx = bisect_left(sequence, A[i]) # lower bound 이분탐색, 대체할 수 있는 자리를 교체
        sequence[idx] = A[i]

sequence.pop(0) # 맨 처음 넣었던 쓰레기값 제거
print(len(sequence)) # LIS 수열이지만 실제로 답에서 요구하는 LIS 수열은 아님

(백준)완전한 LIS 수열 구하기
실제 LIS 수열을 구하기 위해 대체한 자리를 기록하는 디테일을 넣어준다.
모두 기록한 후, 기록된 인덱스 데이터를 역순으로 탐색하여 실제 LIS 수열을 찾을 수 있다.

from bisect import bisect_left

A = [10, 20, 40, 30, 10, 50]

idx_memo = [-1] * len(A)
max_idx = 1
sequence = [-1]

for i in range(len(A)):
	if sequence[-1] < A[i]:
    	sequence.append(A[i])
        idx_memo[i] = max_idx # 현재 수가 LIS 수열에서 몇번째 자리를 차지했나 기록하기
        max_idx += 1 # LIS 수열 길이 기록
    else:
    	idx = bisect_left(sequence, A[i])
        sequence[idx] = A[i]
        idx_memo[i] = idx # 어떤 자리를 대체했는지 기록
        
sequence.pop(0) 
real_seq = []
max_idx -= 1
for i in range(N - 1, -1, -1):
	if idx_memo[i] == max_idx: # max_idx + 1을 차지한 수 이후에 가장 마지막에 max_idx 자리를 차지한 수
    	real_seq.append(A[i])
    	max_idx -= 1

real_seq.reverse() # 역순으로 탐색하였기 때문에 뒤집어 준다.
print(*real_seq)