최장 증가 수열

참고 포스팅 :

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))