LIS는?

Longest Increasing Sequence, 즉 최장 증가 수열을 의미한다. 회로에서 배선을 할 때 교차를 최대한 줄이거나, 데이터 마이그레이션을 하면서 정렬을 하고 싶을 때 LIS 엔티티들만 먼저 옮기고, 나머지만 조작해 주면 작업을 최소화 할 수 있다고 한다.

관련 백준 문제

다양한 문제가 있지만 대표적으로 아래로 정리해볼 수 있다.

• 11053 가장 긴 증가하는 부분 수열: O(n^2)의 DP로 풀 수 있음
• 14002 가장 긴 증가하는 부분 수열 4: 최적해를 실제로 출력해야 함(reconstruct가 포함되는 문제)
• 12015 가장 긴 증가하는 부분 수열 2: O(nlogn)의 이분탐색 알고리즘 조합으로 풀어야 함.
• 12738 가장 긴 증가하는 부분 수열 3
• 2352 반도체 설계

BOJ 11053 / BOJ 12015

가장 기본적인 LIS 문제를 대표로 보도록 하자. n개의 숫자가 주어질 때 LIS를 단순히 구하면 된다. 이는 O(n^2)의 DP로도 풀 수 있지만, 이분탐색을 활용하면 O(nlogn)으로 풀 수 있다.

풀이

def solve(n: int, seq: list) -> int:
    lis = []  # define pseudo lis
    for num in seq:
        pos = bisect_left(lis, num)
        if pos == len(lis):  # if pos is equal to the length of lis
            lis.append(num)  # increase lis itself
        elif pos == len(lis)-1:  # otherwise
            lis[pos] = num
    return len(lis)

위 코드에서 seq 입력값이 아래와 같을 때, lis의 갱신 방향을 보만 다음과 같다.

# seq 입력값
1 10 5 6 9 4 5 6 7 10

# lis 갱신 순서
[1]
[1, 10]
[1, 5]
[1, 5, 6]
[1, 5, 6, 9]
[1, 4, 6, 9]
[1, 4, 5, 9]
[1, 4, 5, 6]
[1, 4, 5, 6, 7]
[1, 4, 5, 6, 7, 10]

이때, 이것이 최적해를 구하는 이유를 이해하기 위해선 bisect_left를 이해해야 한다.
bisect_left(list, num)일때, list에서 num의 위치를 리턴한다. num의 위치를 이분탐색으로 구하고, 같거나 작을 경우는 list의 전체 길이 n보다 작은 값을,
완전히 클 경우 n을 리턴한다.
이런 특성을 LIS 문제에 적용할 수 있다. 선형으로 시퀸스를 탐색하면서 시퀸스의 한 요소의 위치를 구하고, 그 인덱스가 n보다 작다면, 그 새로운 값은 기존의 그 자리에 있던 요소보다 작다는 것을 의미한다.
따라서 lis[pos] = num이 수행될 때마다, '그 자리에 들어갈 수 있는 가장 작은 수'가 갱신되는 셈이고, 덕분에 배열 자체를 선형으로 탐색함에도 최적해를 구할 수 있다.