가장 긴 증가하는 부분수열 (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를 구해보자.
무지성 야생의 힘으로 덤벼보자.
모든 부분수열을 구해서 그 중에서 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 이 된다는 소리다.
이전 단계를 활용하여 다음 단계를 계산가능하다 = 동적 계획법 이란 것을 깨달아야 한다.
동적 계획법을 사용해보자.
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))업그레이드(개선)
이중 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,5]
극한의 효율충
편하자고 만들어놓은 lsi_arr배열 조차 매번 순회하고 있다.
lsi_arr배열에서 현재 값보다 작은 값을 찾아내는 것이 목적이고,
lsi_arr배열은 항상 오름차순으로 정렬되어있다는 점을 이용하여 이분탐색을 이용한다.
lsi_arr= [가장큰정수] * n개를 생성해두고
C++에서는 lower_bound(), Python에서는 bisect_left() 함수를 이용하여 위와 같은 로직을 한번에 구현 가능하다.
파이썬(python) 라이브러리 - bisect (이진탐색, 바이너리 서치, Binary Search)
이진탐색 (바이너리 서치, Binary Search) 정렬된 리스트에서 탐색 범위를 절반씩 좁혀나가며 빠르게 탐색하는 방법 특징 탐색 범위가 매우 크게 주어짐 O(n) 인 선형탐색으로는 시간초과 나는 경우
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))초고수의 경지
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))