LIS (Longest Increasing Subsequence)

SeungHyuk Shin·2021년 4월 9일
0
post-thumbnail

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)
            	
        	
    		

0개의 댓글