[알고리즘,개념,DP] LIS (Longest Increasing Subsequence)

* 이 글은 구글의 다양한 포스팅을 보고난 뒤, Mapin의 방식으로 정리하는 글 입니다. 다양한 블로그들의 개념 글과 흡사할 수 있습니다. 제일 이해가 잘되었던,블로그 포스팅을 refer에 넣겠습니다.

LIS(Longest Increasing Subsequence)

• 어떤 수열에서, 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열
• 이때, 부분 수열의 숫자들은, 원 배열에서 이어져 있지 않아도 된다.
• 예를들어, 수열 A={1,4,6,8,3,5,6,7}에서 증가 부분수열은 S1={1,4,6}, S2={4,6,8} 등등이 있을거다. S1,S2...Sn와 같은 증가 부분수열 중 가장 긴 수열을 LIS라고 한다.
• 이 글에서는 LIS의 길이를 구하는데 초점을 둘거다!

Sol 1. Brute Force(완전탐색)

---

문제를 푸는데 가장 기본적인 방법, 완전탐색이다. 수열 A={1,4,6,8,3,5,6,7}로 문제를 풀어보자.

수열 A에서, 증가 부분수열 중, 하나를 생각해보자.

파워 포인트에서 그려옴

S ={3,5,6,7}으로 생각할 수 있다. 그리고, LIS의 정의를 수학적으로 정의를 내리자면 아래와 같이 표현할 수 있다.

 

• 정수 i,j에 대해서, i<j 이면, S[i]<S[j]이다. (i,j는 i번째,j번째를 이야기한다고 할 수 있음)

구현을 한다면, 일단, 증가 수열의 첫번째 원소,S[0]를 먼저 정한 뒤, 위의 조건에 맞게 재귀적으로 구현을 할 수 있을거 같다. 재귀적으로 구현할 수 있는 이유는, 다음 원소를 구할 때도,S[i]<S[j]라는 조건이 동일 하기 때문이다.

 

그리고, 재귀함수의 Flowchart를 생각해주면, 재귀를 진행하면서, 내 앞의 숫자가 어떤 숫자인지는 필요 없는 정보다.

왜냐하면, 자기가 조건에 맞게 선택이 되었다고 한다면, LIS의 정의에 의해서, 그 뒤에 있는 친구들은 자기 자신보다 작은게 이미 보장되기 때문이다. 그리고, 길이만을 구하기 때문에, 앞의 call에서 길이만 +1 해주면 된다.

 

def Lis(arr):
	if not arr:
    	return 0
    ret=1 #비교할 max값
    for i in range(len(arr)):
    	nxt=[] #시작점이 갱신될 때마다, 새로운 후보군 생성
        for j in range(i+1,len(arr)):
        	if arr[i]<arr[j]:
            	nxt.append(arr[j]) #다음 , LIS가 될 수 있는 후보들
        ret = max(ret,1+Lis(nxt))
    return ret

시간 복잡도

• 재귀는 함수를 부를 때, 계속 2개로 분기점이 생기기 때문에, 직관적으로 O(2^n)임을 알 수 있다.하지만, 직관도 좋은 방법이지만, A={1,2,3}인 수열로 Flowchart를 그리면, 2^n임을 쉽게 알 수 있다.

Sol 2. DP(Dynamic Programming)

---

DP의 방법은 Bottom - up , Top - down 2가지 방식이 있다.

 

Top down

• 완전탐색에서 얻은 아이디어에서, 기록을 해주면서, 반복되는 부분을 줄여나가면 된다.
• 아이디어는 변함이 없음!

#Top -down
# 첫번째 원소에 제일 큰 값이 올 수 있기 때문에, 0번째 인덱스에 음의 무한을 넣어준다.
# 
import math
def Lis(arr):
	arr=[-math.inf] +arr
   	N = len(arr)
        dp =[-1] *N
        def find(start):
            if dp[start] != -1:
                return dp[start]
            ret =0
            for nxt in range(start+1,N):
                if arr[start]<arr[nxt]:
                    ret = max(ret,find(nxt)+1)
            dp[start] = ret
            return ret
         return find(0)

시간복잡도

• dp테이블 1개를 채우는데 반복문 N번, 즉 O(N^2)

Bottom- up

• Bottom - up 방식은, 구현이 좀 다르다.
• 앞에서 생각해주다보면, 결국은 2^n으로 가기때문에, 뒤에서부터, 원소를 정하고 자기보다 작은 원소들을 선택해서, 증가 부분수열을 구성해주는 방법을 채택함. (사실 이게 구현이 제일 쉽다)

#Bottom up
# 뒤에서 부터, 앞에서 이룰 수 있는 LIS 길이를 계속 더하면서, 갱신해준다.

N =int(input())
arr = list(map(int,input().split())
dp = [1]*N

for i in range(N):
	for j in range(i):
    	if arr[i]>arr[j]:
        	dp[i] =max(dp[i],dp[j]+1)
print(max(dp))

 

Sol 3. Binary Searching(NlogN)

---

엥? 왜 뜬금없이 Binary Searching? 형이 왜 거기서 나와? 라는 생각이 들겠지만, 천천히 따라가보면 , 와 쩐다 라는 생각이 드는 엄청난 풀이법이다.

• 수열 A가 있다고 합시다. (단,A의 크기는 정수로 이루어진 수열이라는 것만 압니다)
• 우리는 이 A로 LIS를 구성해야합니다.

A의 일부분을 보니, {7,8,2,3}이라는 부분이 있습니다. LIS는 [7,8] ,[2,3] 이런식으로 구성이 될 수 있습니다.

또 다른 부분을 보니, {5,7,8,2,3...}이라는 부분도 있었습니다. LIS는 [5,7,8]으로 구성이 될 수 있습니다.

 

이때, 현재까지 LIS의 정보를 가지고, 과연 나중의 LIS 정보에 반영을 할 수 있을까 ? 이런식으로 계속 구하다 보면, 과연, 내가 지금까지 구한 LIS정보가 의미가 있을까? 라는 생각이 들게 될겁니다.

• 의미가 없다. [5,7,8]이 LIS라도, 2,3,4,5,6,7,8..등 [2,3]으로 시작할 수 있는 새로운 LIS가 언제든지 나타날 수 있다. 그러므로, [5,7,8]은 의미 없는 정보이다.
• 의미가 있다. [5,7,8,2,3]으로 수열이 끝난다면, [5,7,8]이 LIS지 않느냐, 의미는 있는 행동이였다 !

의미가 있는지 , 없는지 애매하다. 이 애매함을 확실하게 만들기 위해, 우리 이해력이 좋으신 내 또다른 자아 Mapin을 소환해보도록 하자.

크기가 1인 LIS일 때, LIS의 숫자가 작을 수록 LIS를 만드는데 유리하다. 

• Mapin : 끄덕. 통과

크기가 2인 LIS일 때, LIS의 마지막 숫자가 작을 수록 유리하다. 

• Mapin : 끄덕끄덕. 예를들어, [5,7],[1,2],[2,3] ,[4,5] 4가지 크기가 2인 LIS가 있을 때, 뒤에 붙는 원소가 3이라면, [1,2,3]으로 [1,2]만 LIS를 이룰 수 있다.
• Mapin: 잠깐 ! 멈춰! (멈춰!) 어디서 장난질이냐!! 뒤에 3이 왔다고 하자, 그 뒤에 막 어 [100,200,300...1억]이 왔다고 하면, [5,7],[2,3],[4,5]도 뭐 다 가능한거 아니야? ,
• 선생님. 그렇다고해도, 다른 수열들 보다, [1,2]로 시작한게 3이 하나 더 들어가서,길이가 1 더 큽니다.. 
• Mapin: 잠깐,잠깐, 그럼, 뒤에 다시 시작하는 부분이 있다면, 어쩔거야? [1,2] 뒤에 [0,1,2,3,4] 가 있으면, [0,1,2,3,4]가 LIS 아니여 ?!
• 선생님, 저희는 수열을 다 검사해서, 같은 크기의 LIS을 검사하겠죠? 그럼. 당연히 [0,1]이라는 것도 미리 검사가 되지 않을까요..?

그렇다. 결론적으로 "증가 부분수열의 크기가 같다면, 이때 마지막 값의 크기가 작은 것의 정보를 유지하는 것이 유리하다."로 결정이 된다.

 

구현

이제, 이걸 구현하는게 또 다른 문제이다. 크기가 같다면, 마지막 값의 크기가 작은 것의 정보를 유지시켜줘야한다. 

C라는 배열을 하나 선언해서, 이렇게 정의하자.

 

C[i] = 길이가 i인 증가수열(LIS)들 중에서, 최소의 마지막 값

• 배열 크기 자체를 index로 활용하기 위해서, C의 크기는 수열의 크기 +1로 선언해주고, 0번째 값은, -inf,나머지 값들은 최솟값으로 갱신시켜 주기 위해서 inf로 선언해준다.
• 예시를 하나 들면, A=[5,6,7,8,1] 이면, C=[-inf,1,6,7,8,inf]가 될것이다.
• 이렇게 갱신하는 과정을 거치다보면 어느 순간 원소의 끝에 도달할 수 있을테고 ,그때 C[i]에 값이 있다면, 그 i가 LIS의 길이가 되버린다.

결국 ,우리는 C배열을 완성시키는 기나긴 여정을 출발하게 될것이다.

 

순회하는 수를 N, 지금까지 찾은 LIS의 길이를 cnt,C[cnt]의 원소를 last라고 합시다.

N의 크기에 따라서, 우리는 2가지 경우의 수가 발생하게 됩니다.

1. 현재 탐색할 수(N)가 C배열의 마지막 수보다 크다면, 새로운 LIS의 등장이므로, C에 바로 넣어주면 된다.

예를들어, C=[5,6,8,inf,inf,inf]라면, N=10이면, C=[5,6,8,10,inf,inf]로 갱신해주고, LIS는 길이가 4로 바로 갱신이 될거다.[5,6,8,10]이겠죠 ?

 

2. 현재 탐색할 수 (N)이 C[i-1] <N<=C[i]라면, 어떻게 될까요? , 즉, C=[5,6,8,inf,inf,inf]일 때, N=7이 오게 된다면, 

C는 우리가 처음 생각했던데로, [5,6,7]로 갱신을 시켜줘야합니다. 결국 이 index를 갱신하는 과정에서, 정렬되어있는 C이기 때문에, C를 넣을 만한 곳을 찾는데 ,선형탐색을 하지않고, 이분탐색을 통해 index를 찾게 됩니다. 

그래서, NlogN이라는 엄청난 발전된 알고리즘이 딱! 나타나는 겁니다.

 

import sys

def Lis(arr):
	if not arr:
    	return 0
    INF=sys.maxsize
    C=[INF]*(len(arr)+1)
    C[0]=-INF
    C[1]=arr[0]
    len_Lis=1
    # find idx! (C[i-1] <N<=C[i])
    def binary_search(lo,high,n):
    	if lo==high:
        	return lo
        elif lo +1==high:
        	# C=[2,3] ,n=1일떄, C=[1,3]으로 갱신해야함.
        	return lo if C[lo]>= n else high
        mid=(lo+high)//2
        if C[mid]==n:
        	return mid
        elif C[mid]<n:
    		return binary_search(mid+1,high,n)
        else:
        	return binary_search(lo,mid,n)
     for n in arr:
     	if C[len_Lis] <n:
        	len_Lis+=1
            C[len_Lis]=n
        else:
        	nxt_loc=binary_search(0,len_Lis,n)
            C[nxt_loc]=n
      return len_Lis

 

 

refer)

엄청 좋은 글입니다! 꼭 읽어보세요!! 제가 포스팅 한글은 이 블로그에서 보고 따라서 배운걸 정리한 글 입니다!

https://shoark7.github.io/programming/algorithm/3-LIS-algorithms

LIS의 길이를 구하는 3가지 알고리즘

LIS 개념 - 나무위키