LIS (Longest Increasing Subsequence) 최장 증가 부분 수열
최장 증가 부분 수열은 말 그대로 가장 길게 증가하는 부분 수열으로
즉, 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열을 LIS라고 합니다.
좀 더 이해하기 쉽도록 아래 그림을 봅시다.
만약 위와 같은 배열이 있을 때 만들수 있는 증가 부분 수열은 위와 같으며
최장 증가 부분 수열은 만들 수 있는 증가 부분 수열 중 길이가 가장 긴 [1, 2, 6]이 됩니다.
LIS를 구현하는 방법으로는 두가지가 있습니다.
-
Dynamic Programming (동적 계획법)
-
Binary Search (이분 탐색)
DP를 활용한 LIS 구현
DP를 활용할 시 이중 반복문을 사용하여 O(n^2)의 시간 복잡도를 가집니다.
그렇기에 입력 값의 크기가 작을 경우에 유용합니다.
코드(DP)
x = int(input())
# arr=[10,20,10,30,20,50]
arr = list(map(int, input().split()))
# 1로 초기화
dp = [1 for i in range(x)]
for i in range(x):
for j in range(i):
# 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인한다
if arr[i] > arr[j]:
#작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면 된다
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))| arr | 10 | 20 | 10 | 30 | 20 | 50 |
|---|---|---|---|---|---|---|
| dp | 1 | 2 | 1 | 3 | 2 | 4 |
- dp배열의 원소중 가장 큰 원소를 출력한다.
- 정답은 4
이분 탐색을 활용한 LIS 구현
이분 탐색을 활용할 시 O(logn)의 시간 복잡도를 가집니다.
입력 값이 크기가 클 경우 DP를 활용하면 효율이 떨어지기 때문에 이분 탐색을 활용하여 시간 복잡도를 줄일 수 있습니다.
또한 이분 탐색을 활용하는 경우에는 정확한 LIS가 아닌 LIS의 길이를 구할 때 사용됩니다.
import bisect
def LIS_binary_search(arr):
lis = [] # 가장 긴 증가하는 부분 수열을 저장할 리스트
for i in arr:
# lis 리스트에서 i의 위치를 찾아줌. lis에 없으면 i보다 큰 값 중 가장 작은 값의 위치를 반환
pos = bisect.bisect_left(lis, i)
# 만약 pos가 lis의 길이와 같다면, i는 현재 lis에 있는 모든 값보다 크다는 의미이므로 lis에 추가
if pos == len(lis):
lis.append(i)
else:
# 그렇지 않다면, lis의 pos 위치에 있는 값을 i로 교체. i는 lis에 있는 값보다 작거나 같은 첫 번째 값으로 설정
lis[pos] = i
# 최종적으로 lis의 길이를 반환
return len(lis)
# 예제 배열
arr = [3, 5, 7, 9, 2, 1, 4, 8]
print("arr :", arr)
print("LIS 길이 :", LIS_binary_search(arr))
LIS 이분 탐색 과정
블로그 참고
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/LIS%20(Longest%20Increasing%20Sequence).md
https://hstory0208.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-LIS%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4%EC%9D%B4%EB%9E%80
