설명
가장 긴 증가하는 부분 수열 문제, 줄여서 LIS(Logest Increasing Subsequence)라고도 한다.
크게 완전탐색, DP, 이진탐색 방식으로 풀이할 수 있다.
유사한 문제가 여럿 있는데 이 문제는 DP(Dynamic Programming)방식으로도 풀리는 문제이다.
이번에는 위 3가지 방식으로 모두 풀이하겠다.
일단 LIS란 무엇일까?
LIS는 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분 수열 중 가장 긴 수열을 말한다. 꼭 부분수열의 원소들이 배열에 이어져있지 않아도 된다.
완전 탐색
증가 부분수열은 다음 특징을 갖는다.
1. 정수 i,j에 대해 i < j이면, S[i] < S[j]이다.(0 <= i, j <= |S|)
2. 정수 i,j에 대해 S[i] < S[j]이면, 원 배열 arr에서 S[i], S[j] 두 수의 위치 전후관계는 같다. (0 <= i, j <= |S|)
증가 부분수열의 첫번째 수를 선택하고, 그 뒤에 있는 원소 중 큰 값들을 배열에 추려 재귀한다. 큰 값들 입장에서는 첫번째 수가 자신보다 작은 것을 의미한다. 따라서 큰 값들끼리 부분수열을 하여 재귀적으로 이전값의 길이를 1씩 더해니간다.
def lis(arr):
if len(arr) == 0:
return 0
length = 1
for start in range(len(arr)):
next = []
for j in range(start+1, len(arr)):
if arr[start] < arr[j]:
next.append(arr[j])
length = max(length, 1 + lis(next))
return length
print(lis(A))첫 번째 for문: 배열의 시작이 되는 첫번째 수를 선택한다. 완전탐색이므로 배열의 모든 수가 증가수열의 첫번째 숫자가 된다.
두 번째 for문: 첫번째 수 이후부터 LIS가 되는 숫자들을 추린다.
1 + lis(next)는 재귀를 호출할 때 arr[i]의 크기 1만 더해주면서 완성된 증가 부분수열의 길이를 구하도록 한다.
시간복잡도는 어떻게 될까?
LIS(1,2,3)이라는 값을 가지고 표현해보면, lis(3) 호출이 8번 일어났음을 확인할 수 있다. 따라서 2^3 = 8이므로, 완전탐색으로 구현하면 시간복잡도는 O(2^N)를 나타낸다. 이 방식대로 해보니 시간초과가 나왔다.
DP
완전탐색의 문제점은 중복이 발생한다는 점이다. 이 문제점을 동적 계획법으로 해결해보자.
아이디어는 다음과 같다. 코드로 설명하는게 더 좋을 것 같아서 코드를 추가하겠다.
dp = [1] * N # dp가 1로 초기화된 빈 배열 생성
# 첫번째 for문: 시작점
for i in range(1, N):
# 두번째 for문: 0부터 시작점까지 확인하면서, 시작점이 크다면 해당 dp에 시작점+1(`dp[j] + 1`)과 dp[i]를 비교하여 큰 것을 선택한다.
for j in range(i):
if(A[i] > A[j]):
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp)) # 가장 큰 dp 값이 정답이다.
이 방식은 중복을 제거하여 완전탐색보다 좋은 시간복잡도를 갖는다. 하지만 채워야하는 DP가 N이고, 각각 N번의 비교를 하기 때문에 O(N*N)의 시간 복잡도를 갖는다.
이진 탐색
시간 복잡도를 더 줄일 수 있는 방법은 무엇일까?
[10, 20, 10, 30, 40] 이라는 값이 담겨있는 리스트가 있다.
길이가 3인 수열을 만들어 보면 다음과 같다.
1) 10 - 20 - 30
2) 10 - 20 - 40
이때 증가 부분 수열의 크기가 같다면 무엇이 LIS를 만드는데 유리할까? 1번이다.
그 뒤에 40을 붙여 10 - 20 - 30 - 40 이렇게 만들 수 있기 때문이다. 즉 증가 부분 수열 크기가 같다면, 마지막 값의 크기는 작아야 한다.
이 문제도 dp를 사용함은 같다.
핵심은 현재 가리키는 원소보다 작은 원소를 만나면, 이진 탐색으로 dp에 저장된 원소 중 가장 가까운 값을 찾는 것이다.
dp = [0]
def findNearest(key):
left = 1
right = len(dp)-1
while left <= right:
middle = (left + right) // 2
if key == dp[middle]:
return middle
elif key < dp[middle]:
right = middle - 1
elif key > dp[middle]:
left = middle + 1
# 찾지 못했을 때
# 왼쪽 밖으로 나간 경우
if right < 1:
return 1
# 오른쪽 밖으로 나간 경우
elif left > len(dp)-1:
return len(dp)-1
# 사이에 있는 경우
# left와 right 순서가 바뀌었으므로 left가 가리키는 값이 더 큰 값이다.
else:
return left
for i in range(N):
# dp 맨 마지막에 저장된 원소보다 현재 가리키는 원소가 더 큰 경우 -> dp 리스트 맨 뒤에 원소를 추가한다.
if dp[len(dp)-1] < A[i]:
dp.append(A[i])
# dp 맨 마지막에 저장된 원소가 현재 가리키는 원소보다 작은 경우 -> 인접한 원소 중 큰 값이랑 자리를 바꾼다.
else:
dp[findNearest(A[i])] = A[i]
print(len(dp)-1)세 방식으로 모두 확인해보니 확연한 차이를 보였다.
- 완전탐색으로 풀이한 경우: 시간초과
- DP로 풀이한 경우: 160ms
- 이진탐색으로 풀아힌 경우: 44ms
Reference
