1. LIS란?
가장 긴 증가하는 부분 수열 구하기이다. 기본적으로는 다이나믹 프로그래밍을 이용하여 각각의 수를 모두 훑어 비교해가며 한 배열에다가 최장길이의 숫자를 저장하지만 이런 방식을 사용할 경우 시간 복잡도가 O(N^2) 나오므로 배열의 크기가 클 경우 사용 하지 못한다. 따라서 O(NlogN)의 시간복잡도를 가진 알고리즘을 설명려한다.
1-1. LIS 알고리즘 O(NlogN)
우선 기존 배열을 A, 증가하는 부분 수열을 구할 배열을 B라고 하겠다.
A = [10,20,40,25,20,50,30,70,85]
B = [A[0]]알고리즘이 작동하는 방식은 다음과 같다.
- A배열을 돌면서 각 원소를 가져온다.
- 해당 원소가 B배열의 가장 마지막 원소와 비교해 크다면 마지막에 원소를 삽입한다.(즉, B배열의 마지막 원소는 가장 큰 값이다.)
- 작거나 같다면 해당 원소가 들어갈 자리를 B배열에서 이분탐색으로 찾아낸다.
- A배열을 다 돌고난 후 B배열의 크기가 해당 A배열의 LIS가 된다
for a in A:
if a > B[-1]:
B.append(a)
else:
bisect.insort_left(B,a)
print(len(B))
bisect는 파이썬에서 제공하는 표준 라이브러리다. 이진 검색 알고리즘을 이용해서 시퀀스를 검색하는 biesct와, 시퀀스에 항목을 삽입할수 있는 함수 insort를 제공한다.
1-2. LIS의 구성 원소를 알고싶다면?
LIS에 들어가있는 배열의 원소들은 실제 LIS 배열의 원소들과 괴리가있다.
예를들어 주어진 수열 A =[ 1 7 3 2 5 10 3 ] 있다고 할때 실제 정답은 1 2 5 10이지만 1번 풀이의 결과물은 1 2 3 10 이 된다.
따라서 해당 원소가 실제 들어갈수 있는 자리를 저장하는 배열 C를 하나 더 만든다. 해당 배열에는
[ 해당 원소가 들어간 인덱스 : 해당 원소의 값 ]
식으로 값을 저장 해준다. 그 이후 C배열에서 lis배열의 가장 마지막에 들어 갈수 있는 원소 값부터 하나씩 줄여나가며 역순으로 돌면서 출력해주면된다.
for a in A:
if a > B[-1]:
C.append(((len(B)-1),a))
B.append(a)
else:
index =bisect.bisect_left(B,a)
B[index] = a
C.append((index,a))
print(len(B))
index = len(B) - 1
stack = [] #결과값으로 나온 원소들을 저장할 스택
C.reverse() # 정보가 들어있는 해당 배열을 뒤집는다
for e in C:
if e[0] == index: #마지막 인덱스부터 줄여나가면서 해당하는 값이 있으면 가져온다
stack.append(e[1])
index -= 1
stack.reverse()
for x in stack:
print(x)
