LIS(가장 긴 증가하는 부분 수열), python

가장 긴 증가하는 부분 수열이란?

 

가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) 란 오름차순으로 정렬된 부분 수열 중에 가장 긴 것을 말한다.

 

예를 들면 수열이 [10, 20, 5, 30, 15, 50]에서 [10, 20 ,30, 50]이다.

 

 

 

 

 

 

LIS의 길이를 구하는 방법

 

첫 번째로 가장 간단하게 LIS를 구하는 방법은, k번 인덱스에서 0~k-1번째 요소까지 확인하면서 찾는 것이다.

시간 복잡도가 O(n^2)이 나오기 때문에 수열의 길이가 커지면 이 방법은 사용할 수 없다.

 

 

 

 

두 번째 방법은 LIS를 저장하는 별도의 리스트를 만들어서 구할 수가 있다.

수열에서 하나씩 탐색하면서 LIS배열이 비어있다면 집어넣어 준다.

만약 LIS배열이 비어있지 않다면, LIS배열에서 이진탐색으로 추가하려는 수열의 요소보다 크거나 같은 값이 처음 나오는 인덱스를 찾아 그 값을 교체해 준다.

만약 찾은 인덱스가 LIS배열의 길이보다 길다면, LIS배열의 마지막 값보다 크다는 뜻이므로 LIS배열에 추가하여 길이를 늘려준다.

bisect_left를 사용하면 이진탐색으로 현재 값보다 크거나 같은 값이 처음 나오는 위치를 반환해 준다.

이렇게 하면 LIS의 길이가 유지되면서, 추후 나오는 값이 더 긴 수열을 만들 수 있는 가능성을 열어둔다.

LIS배열은 실제 LIS값을 담고 있지 않고 길이 정보만 가지고 있게 된다.

 

 

 

수열이 [10, 20, 5, 30, 15, 50] 인경우 

 

먼저 LIS배열이 비어있으니 10을 넣어준다. 현재까지 LIS의 길이는 1이다.

 

 

 

 

 

 

 

 

bisect_left(LIS,20) = 1이다. 배열의 마지막 값보다 크므로 LIS배열에 넣어준다.

 

 

 

 

 

 

 

 

 

bisect_left(LIS,5) = 0이다. 기존 값이 있던 위치에 교체해준다. 이렇게 되면 기존 LIS인 [10,20]을 유지한 채 첫 번째 값을 5로 바꾸어 추후 더 긴 부분수열이 나올 가능성을 열어두게 된다.

여기서 보이듯이 LIS배열은 길이만 저장할 뿐, 실제 LIS를 저장하고 있지 않다.

 

 

 

 

 

 

 

 

 

bisect_left(LIS,30) = 2이고 LIS 배열의 마지막 값보다 크다는 뜻이므로 추가해 준다. 

실제 LIS는 [10,20,30]이다.

 

 

 

 

 

 

 

 

bisect_left(LIS,15) = 1이므로 LIS배열의 값을 교체해 준다.

 

 

 

 

 

 

 

 

bisect_left(LIS,50) = 3이고 LIS배열 마지막 값보다 크므로 추가해 준다.

실제 LIS는 [10,20,30,50] 이 된다.

 

 

 

 

이렇게 수열의 마지막 값까지 LIS배열에 반영해 주면, LIS배열의 길이가 LIS의 길이가 된다.

 

 

 

 

실제 LIS를 구하는 법

 

위의 LIS배열에서는 길이만 구할 수 있었다.

실제 LIS를 구하기 위해서는 좀 더 복잡한 과정이 필요하다.

LIS배열은 탐색이 진행되면서 계속 덮어 씌워진다. 따라서 LIS배열에 업데이트가 발생할 때 그 수가 원본 수열의 어디에서 왔는지를 저장해야 한다. 그리고 LIS배열의 이전 인덱스를 따로 저장해 두어 나중에 덮어씌워져도 저장된 이전 인덱스를 따라서 역추적해서 구할 수 있다.

 

 

 

 

원본 수열의 어디에서 왔는지를 저장하는 배열을 lis_index

이전 인덱스를 저장하는 배열을 prev라고 하면

 

처음 10은 수열의 0번 인덱스에서 왔으므로 lis_index에 0을 추가해 준다.

처음값은 prev를 업데이트할 필요가 없다.

 

 

 

 

 

 

 

20은 LIS배열에 추가되고 수열의 1번 인덱스에서 왔으므로 lis_index에 1을 추가해 준다. prev배열에는 lis_index에서 이전인덱스를 넣어준다. 이렇게 되면 prev [1] = 0 이 되고, 나중에 추적할 때 부분수열에서 1번 인덱스 이전이 0번 인덱스임을 알 수 있게 된다.

 

 

 

 

 

 

 

 

5는 LIS배열의 첫 번째에 업데이트된다. 이때 lis_index도 같이 업데이트를 해준다. LIS배열의 첫 번째 이므로 prev배열은 업데이트할 필요가 없다.

 

 

 

 

 

 

 

 

30은 LIS배열에 추가되고 lis_index에도 추가해 준다. prev에는 lis_index에서 바로 왼쪽에 있는 값을 넣어준다.

prev [3] = 1로 수열의 3번째 인덱스 이전이 1번째 인덱스임을 알 수 있다.

 

 

 

 

 

 

 

15는 LIS배열의 두 번째에 업데이트되고, lis_index 배열도 업데이트해준다. prev [4] = 2로 업데이트해준다. 

 

 

 

 

 

 

 

 

50은 LIS배열 마지막에 추가되고 lis_index에도 인덱스를 같이 추가해 준다. prev [5] = 3으로 업데이트해준다.

 

 

 

 

 

위 과정을 보면 lis_index배열은 prev배열의 값을 저장하기 위해서 있음을 알 수 있다.

LIS배열에서의 마지막 값은 실제 LIS에서의 마지막 값이다. 따라서 50부터 이전값들을 역추적해 나가면 된다.

 

 

LIS배열의 마지막값 50의 인덱스는 5이다.

prev [5] = 3 이므로 배열의 3번째 인덱스인 30이 LIS에서 50의 이전 수가 된다.

 

 

prev [3] = 1이다. 30 이전 값은 수열의 1번 인덱스인 20 임을 알 수 있다.

 

 

prev [1] = 0이고 20 이전은 10이다.

 

 

prev [0] = -1이므로 0이 첫 번째 인덱스임을 알 수 있다.

 

 

이렇게 구한 [50,30,20,10]을 뒤집게 되면 LIS가 된다. LIS는 [10,20,30,50]이다.

 

 

 

 

python 구현

 

LIS배열, lis_index배열, prev배열을 통해 구현할 수 있다.

 

 

for i in range(n):
    x = arr[i]
    # 이진탐색으로 LIS배열에 들어갈 위치를 찾는다.
    pos = bisect_left(lis,x)

    # 만약 LIS배열의 마지막 값보다 크다면 LIS배열에 추가한다
    if pos>=len(lis):
        lis.append(x)
        # lis_index배열에 인덱스도 같이 저장
        lis_index.append(i) 

    # LIS 배열에서 교체될때
    else:
        lis[pos] = x
        # lis_index배열에 인덱스도 갱신
        lis_index[pos] = i 
    
    # 만약 LIS배열의 첫번째 값이 아니라면
    # prev배열에 lis_index에서 현재 위치의 이전 값을 저장한다.
    if pos>0:
        prev[i] = lis_index[pos-1]

 

먼저 bisect_left를 통해 LIS배열에 들어갈 인덱스를 구한 다음, LIS배열, lis_index배열, prev배열에 업데이트를 해준다

 

 

 

result = []
# LIS의 마지막 인덱스부터 시작
t = lis_index[-1]
while t != -1:
    result.append(arr[t])
    # prev값으로 업데이트 해주면서 역추적
    t = prev[t]

# 마지막으로 결과를 뒤집어준다.
answer = result[::-1]

 

prev값을 역추적하면서 배열에 담고, 배열을 뒤집어주면 LIS가 된다.

 

 

 

 

 

LIS를 구해서 해결할 수 있는 문제

 

[백준] 12738 가장 긴 증가하는 부분 수열 3

[백준] 12738 가장 긴 증가하는 부분 수열 3

 

[백준] 14003 가장 긴 증가하는 부분 수열 5

[백준] 14003 가장 긴 증가하는 부분 수열 5

 

 

[백준] 1365 꼬인 전깃줄

[백준] 1365 꼬인 전깃줄