LIS 란?

LIS(Longest Inceasing Sequence)란?

LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1, 9, 2, 7, 3, 8, 4, 6] 이라는 리스트가 존재할때 여기서 증가하는 부분 수열을 찾아 보겠습니다.

[5, 9], [5, 7, 8], [1, 2, 7, 8] 등등 다양한 증가하는 부분수열이 존재합니다. 이중 가장 길이가 큰 최장 증가 부분 수열은 [1, 2, 3, 4, 6]이 됩니다. 이 최장 증가 부분 수열을 찾는 것이 이 알고리즘의 목표 입니다.

모두 구해보기

LIS를 찾기 위해서 가장 먼저 생각할 부분은 모든 부분 수열을 구한 다음에 가장 길이가 긴 부분수열을 찾으면 됩니다. 위의 리스트를 사용한다면 먼저 5로 시작하는 모든 부분수열을 구해서 가장 긴것을 찾습니다. 다음으로 1로 시작하는 모든 증가하는 부분수열을 찾습니다. 이런식으로 길이 비교를 통해 가장 큰 부분 수열의 길이를 찾습니다. 실제 코드로 확인해 보겠습니다.

def lis(arr):
    if not arr:
        return 0
    result = 1
    for i in range(len(arr)):
        next_arr = []
        for j in range(i+1, len(arr)):
            if arr[i] < arr[j]:
                next_arr.append(arr[j])
        result = max(result, lis(next_arr) + 1)
    return result

코드를 확인해 보도록 하겠습니다. 제일 먼저 나온 if문은 종료 조건입니다. 재귀함수에서 종료 조건이 없거나, 종료조건에 도달하지 못할 경우 무한 루프에 빠질 수 있습니다. 종료조건을 반드시 확인하여 추가해 주어야 합니다. 리스트에 아무것도 없다면 빠져나옵니다.

다음으로 종료조건에 도달하지 않았기 때문에 리스트에는 적어도 하나의 원소가 있습니다. 그렇기에 result를 1로 초기화 하였습니다. 다음으로 next_arr은 증가하는 부분 수열이기 때문에 현재 i번째 값보다 큰 원소의 리스트를 만들어 길이를 비교합니다. 이때 next_arr에는 i번째 값이 제외된 것이기 때문에 1을 더해 길이 비교를 해줍니다. 이렇게 LIS의 길이를 구할 수 있습니다. 하지만 이처럼 재귀 완전 탐색으로 구한 LIS는 시간복잡도가 $O(2^N)$ 가 됩니다. 따라서 코딩 문제에서 전혀 사용이 불가능 합니다.

DP 로 풀기

LIS를 구하기 위해서 DP를 사용해 보겠습니다. 앞에서는 모든 경우의 수를 구했기 때문에 시간 복잡도가 너무 높아졌습니다. DP로 구할 때에는 앞에서부터 LIS 길이를 구하고 다음 원소가 등장 하였을 때 해당 원소를 포함하는 LIS를 구하게 됩니다. 앞의 리스트 [5, 1, 9, 2, 7, 3, 8, 4, 6]가 있을 때 처음에는 [5]만 있기 때문에 LIS의 길이는 1 입니다. 다음 1이 나오면 LIS를 만들 수 없기 때문에 그대로 1 입니다. 다음 9가 나타날 때 [5, 9], [1, 9] 두가지 모두 가능하기 때문에 LIS는 2 입니다. 즉 앞에서부터 각각의 원소가 가지는 LIS를 구해 나가면서 가장 큰 LIS로 업데이트 해나갑니다.

이런 방식으로 전체를 확인해 보도록 하겠습니다. 리스트 lis를 만들어 각 순서에 LIS의 길이를 추가해 놓습니다.

1. 5 : 원소가 하나이기 때문에 lis[0]은 1
2. 1 : 5보다 작기 때문에 lis[1]는 1
3. 9 : 5, 1보다 크기 때문에 lis[2]는 2
4. 2 : 두번째 1보다 크기 때문에 lis[3]는 2
5. 7 : 5, 1, 2보다 크다. lis[3]이 가장 크기 때문에 lis[4] = lis[3] + 1 = 3
6. 3 : 1, 2 보다 크다. lis[5] = lis[3] + 1 = 3
7. 8 : 5, 1, 2, 7, 3보다 크다. lis[6] = lis[5] + 1 = 4
8. 4 : 1, 2, 3보다 크다. lis[7] = lis[5] + 1 = 4
9. 6 : 1, 2, 3, 4보다 크다. lis[8] = lis[7] + 1 = 5

위와 같은 방식으로 업데이트 하여 최대값 5를 가지게 됩니다. 코드를 통해 직접 확인해 보도록 하겠습니다.

def lis_dp():
    lis = [0] * (N + 1)
    rst = 1
    for i in range(N):
        lis[i] = 1
        for j in range(i):
            if arr[j] < arr[i]:
                lis[i] = max(lis[i], lis[j] + 1)
                if rst < lis[i]:
                    rst = lis[i]

    return rst

알고리즘을 확인해 보겠습니다. 먼저 각각의 자리수에 맞는 LIS를 저장하기 위한 리스트 lis를 만들어 줍니다. lis[i]는 자기 자신을 통해 길이가 무조건 1이상 이기 때문에 1로 업데이트 합니다. 그 후 i번째 보다 작은 모든 원소를 확인합니다. i번째 보다 작은 원소를 j번째라고 하고 크기를 비교합니다. 리스트 arr에 대해 arr[j] < arr[i]라면 lis[i] = max(lis[i], lis[j] + 1)로 업데이트 합니다. 이 때 가장 긴 lis를 rst에 따로 저장해 둡니다. 모든 for문이 종료 되었을 때 rst를 반환 해줍니다.

이렇게 구해준 LIS의 시간복잡도는 $O(N^2)$ 로 전체를 탐색한 이전 방법의 시간 복잡도 $O(2^N)$ 보다는 빠르지만 아직 만족할 만한 수준의 시간복잡도가 아닙니다.

이분 탐색으로 풀기

다음으로 이분 탐색으로 LIS를 찾는 방법에 대해 알아 보도록 하겠습니다. 전체 탐색은 매번 LIS를 구해 주어 중복이 많았습니다. DP로 탐색은 i번째 LIS를 구할 때 이전의 LIS를 이미 구해 놓았기 때문에 중복은 줄었지만 아직도 매번 i번만큼 비교하기 때문에 좋은 알고리즘은 아닙니다. 이분 탐색을 통해 중복을 더 줄여 보겠습니다. 컨셉은 다음과 같습니다.

1. 해당 원소가 lis 마지막 원소보다 크다면 원소를 추가
2. 해당 원소가 중간 크기라면 이분 탐색을 통해 lis 업데이트

다음과 같은 방법으로 진행 합니다. 직접 앞의 리스트 [5, 1, 9, 2, 7, 3, 8, 4, 6]로 진행해 보겠습니다. dp로 풀기에서의 lis 리스트에는 해당 번호 까지의 lis길이를 저장해 두었다면 이분탐색에서는 직접 lis를 구현하여 저장해 두었습니다.

1. 5는 원소가 하나이므로 lis = [5]
2. 1은 중간값이기 때문에 lis 업데이트. lis = [1]
3. 9는 lis 마지막 원소보다 크기 때문에 추가 lis = [1, 9]
4. 2는 lis 마지막 원소보다 작기 때문에 lis 업데이트. lis = [1, 2]
5. 7은 lis 마지막 원소보다 크기 때문에 추가. lis = [1, 2, 7]
6. 3은 lis 마지막 원소보다 작기 때문에 lis 업데이트. lis = [1, 2, 3]
7. 8은 lis 마지막 원소보다 크기 때문에 추가. lis = [1, 2, 3, 8]
8. 4는 lis 마지막 원소보다 작기 때문에 lis 업데이트. lis = [1, 2, 3, 4]
9. 6은 lis 마지막 원소보다 크기 때문에 추가. lis = [1, 2, 3, 4, 6]

N = int(input())
arr = list(map(int, input().split()))

def binary_search(lis, start, end, value):
    while start < end:
        mid = (start + end) // 2
        if lis[mid] < value:
            start = mid + 1
        else:
            end = mid

    return end

def lis_bs():
    lis = [arr[0]]
    for i in range(1, N):
        if lis[-1] < arr[i]:
            lis.append(arr[i])
        else:
            pos = binary_search(lis, 0, len(lis), arr[i])
            lis[pos] = arr[i]
    
    return len(lis)
    
print(lis_bs())

세그먼트 트리로 풀기

마지막으로 알아볼 방법은 세그먼트 트리로 문제를 해결하는 것입니다. 세그먼트 트리의 풀이 방법은 아래 링크로 따로 작성하였습니다.

 

2023.09.20 - [알고리즘 설명] - [백준 12015] 가장 긴 증가하는 부분 수열 2