No Limitation
최장 증가 수열 본문
참고 포스팅 :
https://shoark7.github.io/programming/algorithm/3-LIS-algorithms
https://stackoverflow.com/questions/35075862/longest-bitonic-subsequence-in-onlogn-complexity
최장 증가 수열(Longest Increasing Subsequence)은 어떠한 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분 수열(increasing subsequence) 중 가장 긴 수열을 의미한다.
여기서 최장 증가 수열은 반드시 뒤의 숫자가 앞의 숫자보다 더 큰 경우만 의미를 하게 된다.
LIS에서 핵심은
현재 내가 증가시키고 있는 수열에서 다음 수가 더 큰 경우에는 추가를 해주되
더 큰 경우는 아니더라도 더 커질 가능성이 있는 수는 먼저 추가를 해주는 방식이다.
말이 조금 어려운데 다음 예제를 한번 살펴보면
arr = [0, 1, 0, 2, 3, 1, 8, 5, 5, 6, 6]
여기서 증가를 쭉 시켜서
[0, 1, 2, 3, 8] 까지 현재 증가수열을 만들어낸 상태이다.
다음 수는 5가 등장을 하는데 5는 8보다는 작은 수이므로 더 큰 경우는 아니다.
하지만 8을 제외한 이 전 수열에 나오는 모든 값들보다는 더 큰 경우이며 5를 추가하였을 때 앞으로 등장할 수에 대한 대응이 더 잘 진행될 것이다.
그래서 8을 빼고 5를 추가할 경우 이어서 나오는 6을 대응할 수 있게 된다.
다음과 같은 논리로 구축된 알고리즘이 바로 LIS이다.
또한 여기서 중요한 점이 다음 수가 등장하고 해당 수가 증가 수열의 가장 마지막 수를 제외한 나머지보다는 더 큰 지를 확인하려면, 또한 해당 수가 존재하는 지를 확인하려면, binary search를 사용하여 더 연산을 빠르게 증가시킬 수 있다.
다음은 해당 알고리즘을 구현한 코드이다.
arr = [0, 1, 0, 2, 3, 1,8, 5, 5, 6, 6]
def binary_search(arr, end, val) :
low = 0
high = end
## 탐색하는 의미가 없는 경우, 터무늬없이 작거나, 가장 큰 수인 경우
if val < arr[0] :
return 0
if val > arr[end] :
return end+1
## 탐색 시작
while low <= high :
mid = (low+high)//2
if low == high :
return low
else :
if arr[mid] == val : return mid
if val < arr[mid] : high = mid
else : low = mid+1
def lis(arr, n) :
## t는 증가 수열을 이루는 요소들의 목록을 보여줌
t = [0]*n
## 초기 값 설정
t[0] = arr[0]
## 현재 증가수열의 가장 큰 부분을 가리키는 인덱스
end = 0
## lis 길이 기록
lis = [0]*n
##
lis[0] = 1
index = 0
for i in range(1,n) :
## 더 큰 수 등장하는 경우 그냥 반환, 아닌 경우 탐색
index = binary_search(t, end, arr[i])
## 해당 index에 해당하는 값 갱신
t[index] = arr[i]
## 끝점 업데이트 되는 경우 (더 큰 값이 들어온 경우)
if index > end :
end += 1
## 길이 갱신 (+1)
lis[i] = end+1
return lis, t
## 길이 출력
print(lis(arr,11)[0])
## 목록 출력
print(lis(arr,11)[1])
이러한 매커니즘에서 핵심 알고리즘만 추려서 다시 구현한 결과는 다음과 같다.
N = int(input())
arr = []; m = 0;
for i in range(N) :
m = int(input())
arr.append(m)
def b_search(low,high,arr, val) :
while(low<=high) :
if low == high :
return low
mid = (low+high)//2
if arr[mid] > val :
high = mid
if arr[mid] < val :
low = mid+1
if arr[mid ] == val :
return mid
def lis(arr,n) :
lists = [arr[0]]
index = 0
for i in range(1,n) :
if lists[len(lists)-1] < arr[i] :
lists.append(arr[i])
else :
index = b_search(0, len(lists)-1, lists, arr[i])
lists[index] = arr[i]
return lists
print(lis(arr,N))
'Algorithm, Data Structure' 카테고리의 다른 글
[최단경로 알고리즘] Dijkstra Algorithm (0) | 2022.02.21 |
---|---|
[Dynamic Programming] - Memoization (0) | 2022.02.02 |
[UnionFind] DisjointSet 찾기 (0) | 2022.01.31 |
[Hash란] - 자료구조 (0) | 2022.01.30 |