[백준 11053번] (bisect)가장 긴 증가하는 부분 수열(LIS) in python

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

---

LIS! Longest Increasing Subsequence로 뜻은 가장 긴 증가 부분수열이다.

별거 없다. 다음 숫자가 자신보다 크거나 같으면 된다.

여기서 두가지로 나뉜다.

 

다음 숫자가 자신보다 크거나 같으면, 단조 증가 (1,1,2,2,3,4)

다음 숫자가 자신보다 무조건 크면, 순증가 (1,2,3,4)

피보나치 수열이 초반 (1,1,2,3,5~~~)로 증가하니 이는 단조증가에 해당한다.

 

이 LIS문제는 다이나믹 프로그래밍에서 유명한 문제이다. 

그렇다면 보통 재귀함수로도 풀 수 있다는 소리.

하지만 그러면 2^n이 되므로 시간복잡도가 증가한다.

 

그렇기에 다이나믹 프로그래밍으로 풀으란 소리인 것 같다.

가장 기초적인 LIS 문제이므로 여기저기 검색하면 많이 나온다.

그 중 https://shoark7.github.io/programming/algorithm/3-LIS-algorithms 이분의 설명이 젤 잘되어 있는 것 같다.

또한 알고리즘 측면으로는 https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4#s-3.2

나무 위키도 괜찮다.

 

자 이제 문제를 해결해보자.

10, 20 10, 30, 20, 50 이다.

리스트 내부를 거칠 때마다 cnt해주는 방식으로 진행하면 된다.

 

1. 숫자를 시작할 때마다 cnt=1을 놔준다.

10	20	10	30	20	50
1

 

2. 다음 숫자로 넘어가서 for문을 돌려 만약 이전 숫자들보다 크면, 이전 숫자의 cnt+1과 현재 cnt=1 중 가장 큰 것을 현재 cnt에 넣어준다. 

10	20	10	30	20	50
1	2

 

3. 다음은 이전 숫자들보다 크지 않으므로 이번 인덱스에서 시작햇을 때 cnt=1한 것을 그대로 놔둔다.

10	20	10	30	20	50
1	2	1

 

4. 30인 숫자로 넘어왔다. for문을 돌려 이전 숫자들보다 큰지 세어보자.

인덱스 0일 때, 숫자는 10이므로 30이 더 크다. 그러므로 10의 cnt+1과 현재 cnt=1 중, 10의 cnt+1이 더 크므로(2) 현재 cnt는 2가 된다. 다음으로 숫자 20을 보자. 숫자 20보다 30이 더 크다! 그러면 또 20의 cnt+1=3, 현재 cnt=2가 되므로 현재 cnt에 3을 넣어준다. 다음 숫자인 10. 30이 더 크다. 10의 cnt+1=2, 현재 cnt=3이므로 현재 cnt=3이 그대로 남는다.

10	20	10	30	20	50
1	2	1	3

 

5.6. 이런식으로 진행하다보면 리스트의 끝까지 왔을 때 모든 cnt가 채워진다.

10	20	10	30	20	50
1	2	1	3	2	4

 

최종으로 cnt중 가장 큰 값을 찾아서 출력해주면 이 수열의 LIS의 길이는 4가 된다.

N=int(input())
lst=list(map(int, input().split()))
cnt_lst=[0]*N

for i in range(N):
  cnt_lst[i]=1
  for j in range(i):
    if lst[j]<lst[i]:
      cnt_lst[i]=max(cnt_lst[j]+1,cnt_lst[i])

print(max(cnt_lst))

 

자 그런데 여기서 이 코드의 시간 복잡도는 N^2이다. 

왜냐면 N의 for문을 N까지 for문을 한번 더 돌렸기 때문읻자. 그러면 N^2이 되니깐.... 이것은 완전탐색이다.

 

그렇다면 약간 이 코드를 수정해서 for문을 한번만 돌리면서 자신보다 숫자가 크면 넣고, 작으면 작은 곳에 넣어주는 방식으로 바꾸면 되지 않을까. == 라는 생각을 알고리즘 고인물들이 했다.

바로 이진탐색이다.ㄷㄷ

 

아까 나무위키의 맨 밑 방법이다.

이 방법을 매우! 쉽게! 알고리즘화하신 분이 있었다.

https://claude-u.tistory.com/442 똑똑한 사람은 너무 많아ㅜ

 

이 분의 코드를 써봤다.

N=int(input())
lst=list(map(int,input().split()))
dp=[]

from bisect import bisect_left

for i in lst:
  k=bisect_left(dp,i)
  print(k)
  if len(dp)<=k:
    dp.append(i)
  else : 
    dp[k]=i

print(dp)

코드에 bisect라는 이진탐색 라이브러리를 사용하셨다. bisect는 이진탐색을 이미 라이브러리로 쫘놓은 함수인데,

bisect_left, bisect_right 함수들은 인자로 리스트와 찾을 값을 넣어준다. 그러면 아웃풋으로 그 값에 대한 인덱스 값을 찾아주는 함수이다.

예를 들어 bisect_left([1,2,3,4],2) 인 경우 [1,2,3,4]에서 2인 인덱스를 이진탐색으로 찾아준다. 여기서 2의 인덱스는 1이다.

하지만 bisect_right인 경우 2를 반환해준다. bisect_right의 경우 찾은 값의 다음 인덱스를 반환해준다.

 

여기서 난 착각한게 있었다. bisect_left([3,5,7,9],4)를 찾을 때 당연히 인덱스는 0일 줄 알았다. 3과 5사이이고 왼쪽 인덱스를 반환하니깐... 이라고 잘못 생각했다.

아니다. bisect_left든 bisect_right든 그 사이의 값을 찾을 땐, 무조건 다음 인덱스를 찾아준다. 즉 3과 5의 인덱스인 0과 1 중 1을 반환해준다는 소리이다.

 

 

그렇게 위의 코드에

3, 5, 7, 9, 2, 1, 4, 8 을 넣었을 때 결과로 1,4,7,8이 나오게 된다!(나무위키의 결과값과 같다!)

 

이진탐색은 logN의 시간복잡도를 가진다. 여기서 for문으로 N을 한번 돌렸으므로, NlogN이 시간복잡도가 된다.

아까의 완전탐색인 N^2보다 훨씬 줄어든 것을 볼 수 있다.