파이썬(python) 가장 긴 증가하는 부분수열 (LIS)

가장 긴 증가하는 부분수열 (LIS)

알고리즘 분류 : 동적계획법

 

설명

---

[3,5,7,9,2,1,4,8] 과 같은 하나의 수열은 여러 부분수열로 나눌 수 있다.

ex) [3,5], [5,7], [9,2,1,4], [1,4,8]

 

그 부분수열의 처음~끝까지 증가하는 횟수가 몇번이 되는지 count 하였을때

가장 횟수가 많은 부분수열을 구하는 문제다.

[3,5]  = 2회

[3,5,7] = 3회

[3,5,7,9] = 4회

[2,1,4] = 2회

 

아이디어

---

[3,5,7,1] 라는 수열의 LIS를 구해보자.

1. 무지성 야생의 힘으로 덤벼보자.
   모든 부분수열을 구해서 그 중에서 LIS를 구한다.
   [3], [5], [7], [1],
   [3,5], [5,7], [7,1]
   [3,5,7], [3,5,1], [5,7,1],
   [3,5,7,1]
   
   모든 경우를 구해보니 비로소 중복된 것이 보인다.
   [3,5] = 2를 미리 구했고, 5보다 7이 크므로 [3,5,7] = 3이 바로 튀어나올 수 있다.
   [엄청많은수..., 5] = 2 라는 것을 구한 상태에서, 그 다음 수가 7이 온다면 2+1 = 3 이 된다는 소리다.
   이전 단계를 활용하여 다음 단계를 계산가능하다 = 동적 계획법 이란 것을 깨달아야 한다.
   
   
2. 동적 계획법을 사용해보자.
   1) dp[i] 정의하기
   [3,5] = 2 → 5가 마지막에 오는 수열
   [3,5,7] = 3  → 7이 마지막에 오는 수열
   즉, dp[i] = i번째 숫자를 마지막으로 하는 LIS 로 둘 수 있다.
   
   2) dp 초기값 설정
   자기자신으로 이루어진 수열은 길이가 1이므로, 길이가 n인 수열은
   dp = [1]*n 로 초기화 해준다.
   
   3) dp 테이블 채우기 O(N^2)
   dp 테이블의 정의대로 채워주면 된다.
   나보다 앞에 있으면서, 값이 작은 것 중에 가장큰 LIS값 + 1(나) 로 채워줄 수 있다.
   "간단히 이중 for문 선에서 처리 가능" 
   

   dp[cur] = max(dp[cur] dp[front]+1)
   
   cur = 현재 idx
   front = 나보다 앞의 idx

   import sys
   n = int(sys.stdin.readline())
   arr = list(map(int, sys.stdin.readline().split()))
   dp = [1]*n
   for cur in range(1, n):
       for front in range(0, cur):
           if arr[front] < arr[cur]:
               dp[cur] = max(dp[cur], dp[front]+1)
   print(max(dp))

3. 업그레이드(개선)
   이중 for문을 돌면서 똑같은 부분을 중복해서 읽고 있다는 생각이 들었을 것이다.
   [1,5,3,6,4] 의 LIS를 찾을 때 아래와 같이 줄줄이 모두 비교해야한다.
   

   1
   1 5
   1 5 3
   1 5 3 6
   1 5 3 6 4
   dp = [1,2,2,3,3]

   
   굳이 그럴 필요 있을까?
   6차례가 되었을때 내 앞에 [1,5] 가 오든 [1,3]이 오든 그건 중요하지 않다.
   뭐가 오든 6을 붙일 수 있다.
   중요한 것은 [1,5] = 2 이고 [1,3] = 2 라는 정보다.
   [1,3]=2 라는 정보를 기록해두었다면, 내가 3보다는 크니 2+1=3 을 얻을 수 있다.lsi_arr[i] = 길이가 i인 LIS 중에서 마지막 값이 가장 작은 것
   이 mem 배열을 추가로 업데이트하며 진행하면 불필요한 비교를 하지 않아도 된다.
   

   arr = [1 5 3 6 4]
   lsi_arr = []
   
   1 차례 : lsi_arr이 비었으니 1을 넣는다.
   5 차례 : lsi_arr[0]=1 보다 크므로 mem에 5를 넣는다.
   3 차례 : lsi_arr[0]=1 보다 크고 mem[1]=5 보다 작다.
            lsi_arr는 가장 작은 숫자가 와야하니 lsi_arr[1]=3 이 된다.
   6 차례 : lsi_arr[1]=3보다 크므로 mem을 추가한다.
   4 차례 : lsi_arr[2]=4보다 크므로 mem을 추가한다.
   
   결과 : lsi_arr = [1,3,4]

4. 극한의 효율충
   편하자고 만들어놓은 lsi_arr배열 조차 매번 순회하고 있다.
   lsi_arr배열에서 현재 값보다 작은 값을 찾아내는 것이 목적이고,
   lsi_arr배열은 항상 오름차순으로 정렬되어있다는 점을 이용하여 이분탐색을 이용한다.
   
   lsi_arr= [가장큰정수] * n개를 생성해두고
   C++에서는 lower_bound(), Python에서는 bisect_left() 함수를 이용하여 위와 같은 로직을 한번에 구현 가능하다.

   파이썬(python) 라이브러리 - bisect (이진탐색, 바이너리 서치, Binary Search)

   import sys, bisect
   n = int(sys.stdin.readline())
   arr = list(map(int, sys.stdin.readline().split()))
   inc_arr = [sys.maxsize]*n
   
   for i in range(0,n):
       idx = bisect.bisect_left(inc_arr, arr[i])
       inc_arr[idx] = arr[i]
   print(bisect.bisect_left(inc_arr, sys.maxsize))

5. 초고수의 경지
   LIS 길이와 그때의 수열이 무엇인지까지 구해보자.
   핵심 포인트는 lsi_arr 배열을 업데이트 할때의 그 인덱스를 별도의 배열로 관리하는 것이다.
   그러면 값들이 어느 순서로 들어갔는지 알 수 있다.
   
   idx_arr = [0 1 0 2 2 3] 이렇게 저장되었을 경우
   배열을 끝에서부터 시작까지 반대로 순회하며 
   3이 처음으로 등장하는 인덱스 = 5
   2가 처음으로 등장하는 인덱스 = 4
   1이 처음으로 등장하는 인덱스 = 1
   0이 처음으로 등장하는 인덱스 = 0 (이미 인덱스 2는 지나쳐왔기 때문에 0임)
   이 순서로 arr배열에서 뽑아내면 그게 LIS이다.
   

   import sys, bisect
   n = int(sys.stdin.readline())
   arr = list(map(int, sys.stdin.readline().split()))
   lsi_arr = [sys.maxsize]*n
   idx_arr = [0]*n
   
   for i,cur in enumerate(arr):
       insert_pos = bisect.bisect_left(lsi_arr, cur)
       lsi_arr[insert_pos] = cur
       idx_arr[i] = insert_pos
   
   lsi_length = bisect.bisect_left(lsi_arr, sys.maxsize)
   
   # lsi의 요소 출력하기
   result = []
   end = max(idx_arr)
   for i in range(n-1,-1,-1):
       if idx_arr[i]== end:
           result.append(arr[i])
           end-=1
   result.reverse()
   for i in result:
       print(i, end=" ")

 

문제 풀이 예시

---

백준 11053번 : 가장 긴 증가하는 부분 수열

 

문제 :

수열 A의 LIS 구하라

 

입력 :

수열 A의 크기 N (1<= N <= 1000)

수열 (1<= Ai <= 1000)

 

출력 :

수열 A의 LIS 길이

 

A   = {10, 20, 10, 30, 20, 50}

LIS = {10, 20, 30, 50} 

 

O(N^2)

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1]*n
for cur in range(1, n):
    for front in range(0, cur):
        if arr[front] < arr[cur]:
            dp[cur] = max(dp[cur], dp[front]+1)
print(max(dp))

O(N logN)

import sys, bisect
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
inc_arr = [sys.maxsize]*n

for i in range(0,n):
    idx = bisect.bisect_left(inc_arr, arr[i])
    inc_arr[idx] = arr[i]
print(bisect.bisect_left(inc_arr, sys.maxsize))

 

11053번: 가장 긴 증가하는 부분 수열

12015번: 가장 긴 증가하는 부분 수열 2

12738번: 가장 긴 증가하는 부분 수열 3

14002번: 가장 긴 증가하는 부분 수열 4

14003번: 가장 긴 증가하는 부분 수열 5

17411번: 가장 긴 증가하는 부분 수열 6

18837번: 가장 긴 증가하는 부분 수열 K

18838번: 가장 긴 증가하는 부분 수열 k