[Algorithm] 최장 증가 부분 수열 (LIS)

💡 LIS 알고리즘 이란?

최장 증가 부분 수열 : LIS (Longest Increasing Subsequence)

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중,
각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 LIS 라고 한다.
동적 계획법 (Dynamic Programming) 알고리즘을 응용한 알고리즘이다.

예를 들어, 다음과 같은 수열이 있다고 하자.

Ex) 10 20 30 10 20 40 50

이 수열에서 증가하는 부분 수열은 여러개 찾을 수 있다. 이를테면
10 20, 10 20 30, 10 20 40, 10 20 30 40, 10 20 30 40 50.. 등 아주 많다.

또, 부분 수열은 꼭 연속일 필요가 없다.

이 때, 위의 수열에서 가장 긴 증가하는 부분 수열은 10 20 30 40 50 이다.
따라서 LIS의 길이는 5가 된다. 하나의 수열에서 LIS는 하나로 정해지지 않을수도 있다.

---

🛠️ $O(N^2)$ 풀이법

백준 11053번(Silver 2) : 가장 긴 증가하는 부분 수열 1
(https://www.acmicpc.net/problem/11053)

# 백준 11053 가장 긴 증가하는 수열(Longest Increasing Subsequence)
from sys import stdin
read = stdin.readline

n = int(read().rstrip())
a = list(map(int,read().rstrip().split()))

# LIS[i]: a[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분 수열의 길이
LIS = [ 1 for _ in range(n) ]

for i in range(1,n):
    for j in range(i):
        if a[i] > a[j]:
            LIS[i] = max(LIS[i], LIS[j]+1)
 
print(max(LIS))

이중 반복문을 통해서 모든 리스트를 탐색하는 방법이다.
입력으로 n개의 데이터를 받기 때문에 $O(N^2)$ 의 시간복잡도를 가진다.

if a[i] > a[j]: LIS[i] = max(LIS[i], LIS[j]+1)

다음 코드를 통해 수열이 증가한다면 $dp$ 테이블에 갱신한다.

---

🔎 $O(N^2)$ 역추적(backtracking)

이번에는 만들어진 $dp$ 테이블을 이용해서 실제 가장 긴 증가하는 부분 수열을 출력 할 수 있다.

백준 14002번(Gold 4) : 가장 긴 증가하는 부분 수열 4
(https://www.acmicpc.net/problem/14002)

# 백준 14002 가장 긴 증가하는 부분수열 4 (Longest Increasing Subsequence)
import sys
read = sys.stdin.readline

n = int(read().rstrip())
a = list(map(int,read().rstrip().split()))

# LIS[i]: a[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분 수열의 길이
LIS = [ 1 for _ in range(n) ]

for i in range(1,n):
    for j in range(i):
        if a[i] > a[j]:
            LIS[i] = max(LIS[i], LIS[j]+1)

# 역 추적 시작
list = []
result = max(LIS)

for i in range(n-1,-1,-1): # 거꾸로 탐색 하면서
    if LIS[i] == result:
        list.append(a[i])
        result -= 1

list.reverse()
print(max(LIS))
print(*list,sep=' ') 

list 라는 결과값을 담을 빈 배열을 선언하고 $dp$ 의 최댓값을 result 변수에 담아주고, 역순으로 인덱스를 돌아보며 부분 수열을 찾는다.

이쯤에서 드는 의문점,

근데 왜 역순으로 추적하는가? 정방향으로 하면 안되나?

정방향으로 (인덱스가 가장 작은 것부터 오름차순으로) 추적하면 안 되는 이유는
만약 5 4 3 2 1 2 3 라는 수열을 입력받았을 경우, 결과 값으로 $dp$ 는 1 1 1 1 1 2 3 이 된다. 그렇게 되면 가장 긴 증가하는 부분 수열의 답으로 5 2 3 이 출력이 된다.

근데 5 2 3 이 실제로 가장 긴 증가하는 부분 수열인가?

아니다, 우선 이 경우엔 증가하는 수열이 아닐 뿐더러, 저 로직으로 문제를 풀게 될 경우 무조건 오답을 도출한다. 그 이유는 정방향 기준 가장 처음 만나는 $dp$ 값이 실제 LIS의 값이 아닐 수 있기 때문이다.
하지만 정방향 기준 가장 마지막으로 만나는 $dp$ 값은 실제 LIS 값 일수 밖에 없다. 다음 표를 보자.

$index$	0	1	2	3	4	5	6
Input	5	4	3	2	1	2	3
$DP$	1	1	1	1	1	2	3

동일하게 1 을 값으로 갖는 $dp$ 값이 많은데,

여기서 핵심은 처음 만나는 0번째 인덱스이냐, 가장 마지막에 만나는 4번째 인덱스이냐 이다.
이미 결과로 봐서 알겠지만, 처음 만나는 값을 기준으로 하면 결과는 5 2 3 이 되고,
마지막에 만나는 값을 기준으로 하면 결과는 1 2 3 이 된다.

그러므로 역순으로 추적하면서, 가장 처음 만나는 $dp$ 값에 해당하는 인덱스로 입력받은 배열의 해당 인덱스에 접근해 실제 LIS 값을 list에 저장한다.

여기서 주의할 점은 역순으로 탐색했기 때문에 배열에도 원소가 역순으로 저장되어 있다.

list.reverse()

다음 코드를 통해서 다시 정방향으로 배열 후 출력하도록 하자.

---

🪚 $O(N * log N)$ 풀이와 역추적

입력 받는 수열의 크기가 갑자기 엄청나게 커진 경우, O(N^2)의 알고리즘으로는 시간 내에 해결할 수 없다.
다음 14003번 문제가 그러하다.

백준 14003번(Platinum 5) : 가장 긴 증가하는 부분 수열 5
(https://www.acmicpc.net/problem/14003)

# 백준 14003 가장 긴 증가하는 부분 수열 5 (LIS : Longest Increasing Subsequence)
from sys import stdin
read = stdin.readline

# 문제의 최소 범위보다도 더 작은 수
INF = -1000000001

# 수열의 크기
N = int(read())
nums = list(map(int,read().split()))
LIS = [INF]
LIS_total = [[INF,0]]

def binary_search(arr, target):
    start = 0
    end = len(arr) - 1

    # 같은 숫자가 들어올 수도 있기에 
    while start < end:
        mid = (start + end) // 2

        if target > arr[mid]:
            start = mid + 1
        # 같은 숫자가 여러개 라면, 가장 왼쪽 인덱스까지 탐색함
        else:
            end = mid

    return end

for num in nums:
    # 수열을 순회하며 나오는 숫자가 LIS의 마지막 원소 보다 크다면
    if num > LIS[-1]:
        LIS_total.append([num, len(LIS)])
        LIS.append(num)

    else:
        idx = binary_search(LIS, num)
        LIS_total.append([num, idx])
        LIS[idx] = num

# LIS 완성 -> 역추적 시작
result = []
LIS_length = len(LIS) - 1

while LIS_total and LIS_length:
    num, idx = LIS_total.pop()

    if idx == LIS_length:
        result.append(num)
        LIS_length -= 1

print(len(result))
print(*result[::-1])

기존의 LIS 알고리즘으로 풀기엔 입력의 크기가 최대 1,000,000 으로 너무 크다.
수열을 순회하며 나오는 숫자가 현재까지 만든 LIS 마지막 숫자보다 작다면, 교체해줄 자리를 전부 탐색하지 말고 이분 탐색을 통해 시간복잡도를 $O(N * log N)$ 으로 줄여야 한다. (싫다면 시간초과 맛좀 볼래?)

이분 탐색을 위한 배열 : LIS
LIS를 구하기 위해 사용한 배열 : LIS_total , 이 배열에는 num을 LIS에 추가 할 당시의 인덱스 값이 같이 저장 되어있다.

나중에 테스트 케이스로 LIS 배열을 출력해보면 LIS 배열만으로도 가장 긴 증가하는 부분 수열을 구한 것 처럼 보이지만, 출력값은 우연이고 실제로 가장 긴 증가하는 부분수열을 구할 수 없다. (가장 긴 증가하는 부분 수열 2 문제를 참고해라!)