[알고리즘] LIS(최장 증가 부분 수열), 응용 문제 3가지

2024년 4월 16일

LIS (최장 증가 부분 수열)

 

최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이란, 주어진 배열 내에 존재하는 여러 부분 수열 중 오름차순을 준수하며 가장 길게 나열되어 있는 부분 수열을 의미한다. 

 

예를 들어, { 2, 3, 8, 6, 4, 5, 9, 1 } 라는 배열의 LIS는 { 2, 3, 4, 5, 9 } 이며 길이는 5 이다.

오름차순을 준수하는 부분 수열은 { 2, 3 }, { 2, 3, 5 }, { 2, 3, 6, 9 } 등 많지만,

가장 긴 부분 수열은 { 2, 3, 4, 5, 9 } 이다.

 

LIS의 길이를 알아내는 방법은 대표적으로 완전 탐색법과 DP(다이나믹 프로그래밍), 이분 탐색이 존재한다.

이 중, 완전 탐색을 통해 모든 부분 수열의 경우를 확인하는 방법은 2^N의 시간복잡도( N = 전체 배열의 길이 )를 가지기에 데이터 값이 조금이라도 많아지는 순간 지옥을 경험하게 된다.

 

효율면에서 개선한 방법이 DP를 응용한 방법이며, DP에서 더 효율적인 시간복잡도를 가지는 방법이 이분 탐색 방법이다.

 

 

DP (다이나믹 프로그래밍)

 

DP 방식의 핵심은 이전에 얻은 결과를 다시 가져와 불필요한 계산을 줄이는 데에 있다.

 

LIS의 길이를 알아내는데 DP를 어떻게 활용할 수 있을까?

우리가 알고 싶은 것은 오름차순을 준수하는 부분 수열 중 가장 긴 부분 수열이다.

위 예시 배열을 다시 한번 보자.

 

2

3

8

6

4

5

9

1

 

만약 4번째 인덱스 값인 4로 끝나는 증가 부분 수열 중 가장 긴 경우를 생각해보자. 그렇다면 해당 부분 수열의 맨 마지막 값을 제외한 모든 값들은 4보다 작아야 할 것이다.

 

이는 곧 4보다 작은 4번째 인덱스 이전의 값들 중, 가장 긴 증가 부분 수열의 경우에 원소 4를 부분 수열의 맨 끝에 추가하면 그것이 현재 탐색 중인 값으로 끝나는 가장 긴 증가 부분 수열이 될 것이다.

 

이를 통해 유도할 수 있는 점화식은 다음과 같다.

 

arr : 전체 배열
DP : 각 원소가 마지막으로 오는 LIS의 길이 정보를 담는 배열. arr[N]이 존재할 때, DP[N]은 arr[N]이 마지막으로 오는 LIS의 길이.

특정 인덱스 번호 T가 존재할 때,

DP[T] = arr[0], arr[1], ... , arr[T - 2], arr[T - 1] 중
arr[T]보다 값이 작은 수가 마지막 원소로 오는 가장 긴 증가 부분 수열의 길이 중 가장 긴 값 + 1

 

 

배열의 맨 앞에서부터 다시 탐색해보자.

 

0번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

arr는 전체 배열이며, DP의 각 인덱스 값은 arr의 해당 인덱스 값이 가장 마지막 원소가 되는 증가 부분 수열 중 가장 긴 경우의 길이를 담고 있다.

 

0번째 인덱스이므로 2가 마지막 원소가 되는 증가 부분 수열 중 가장 긴 경우는 { 2 } 로 길이는 1이다.

따라서 DP[0] 에 1을 저장한다.

 

 

1번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

1번째 인덱스 값인 3이 마지막 원소가 되는 증가 부분 수열 중 가장 긴 수열은,  해당 경우의 수열에서 마지막 원소 3을 제외한 앞의 모든 수는 3보다 작아야 할 것이다.

 

이전까지 탐색한 값인 3보다 작은 수인 2가 마지막 원소로 오는 증가 부분 수열 중 가장 긴 수열의 경우에 3을 이어붙인 길이가 바로, 1번째 인덱스 값이 마지막으로 오는 증가 부분 수열의 길이 중 가장 긴 경우의 길이와 같다. ( = { 2 } + { 3 } )

 

따라서 DP[1]의 값은 DP[0] + 1 = 2가 된다.

 

 

2번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

2번째 인덱스 값인 8이 마지막 원소가 되는 증가 부분 수열 중 가장 긴 수열 또한, 앞에서 탐색한 값들 중 8보다 작은 수가 마지막 원소로 오는 증가 부분 수열의 길이 중 가장 긴 경우의 길이에 1을 더한 수를 DP[2]에 대입하면 된다.

 

3번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

3번째 인덱스 값인 6이 마지막 원소가 되는 증가 부분 수열 중 가장 긴 수열 또한, 앞에서 탐색한 값들 중 6보다 작은 수가 마지막 원소로 오는 증가 부분 수열의 길이 중 가장 긴 경우의 길이에 1을 더한 수를 DP[3]에 대입한다.

 

이런 방식으로, 현재 탐색 중인 특정 인덱스의 값으로 끝나는 LIS의 길이는 해당 인덱스의 앞쪽에 있는 각각의 경우의 수 중, 탐색 중인 값보다 작으면서 가장 길이가 긴 경우에 1을 더한 값(자기 자신을 추가한 값)이 된다.

 

따라서 주어진 배열에 존재하는 LIS의 길이는 각 원소를 마지막으로 하는 부분 LIS 값들 중 가장 긴 길이를 도출해내면 된다.

 

계속 탐색을 진행해보겠다.

4번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

 

5번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

6번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

7번째 인덱스 값이 가장 마지막으로 오는 최장 증가 부분 수열 길이

 

배열의 마지막 요소까지 탐색을 완료하였다.

 

해당 로직을 통해 알 수 있는 LIS의 길이는 DP 배열에서 가장 큰 값인 5가 된다.

 

만약 LIS의 구성 요소들까지 알고 싶다면, DP의 각 요소에 LIS의 길이와 LIS 구성 요소까지 2차원 배열 형태로 저장하면 된다.

(예. DP = [ [1, [2]], [2, [2, 3]] , [3, [2, 3, 8]] , [3, [2, 3, 6]] , ... ]

 

 

시간복잡도

 

DP를 활용한 LIS 알고리즘의 시간 복잡도는 모든 배열의 요소를 순차적으로 탐색하고( O(N) ), 각 요소를 탐색할 때 그 앞의 요소들에 대해 한 번 더 탐색을 진행( O(N) )해야 하므로 O(N^2) 이다.

 

---

 

이분 탐색

 

DP의 경우, 완전 탐색보다 훨씬 더 효율적인 방법이지만 결국 시간복잡도가 O(N^2) 이기에 데이터의 크기(배열의 길이)가 커지면 쉽게 부담을 느끼게 된다.

 

이를 해소하기 위해 이분 탐색을 활용할 수 있다.

 

 

이분 탐색을 활용한 LIS의 길이를 알아내는 과정은 다음과 같다.

 

arr : 전체 배열
lis : 특정 길이만큼의 증가 부분 수열이 존재할 때, 각각 마지막 원소로 올 수 있는 값.
예를 들어, lis[1] = 3이라면 길이가 2인 증가 부분 수열 경우의 수 중 마지막 원소의 최솟값이 3이라는 뜻.

위와 같이 정의할 때, 흐름도는 다음과 같다.

1. arr의 맨 앞에서부터 마지막까지 탐색을 진행할 것이다.

2 - 1. arr의 특정 요소를 탐색할 때, lis의 마지막 요소보다 크거나 lis 배열이 비어있는 경우 lis의 마지막에 탐색 중인 arr의 값을 추가한다.

2 - 2. arr의 특정 요소를 탐색할 때, lis의 마지막 요소보다 작다면 lis 배열을 이분 탐색하여 탐색 중인 arr의 값이 들어갈 수 있는 위치에 치환시킨다.
치환하는 위치는 lis[T - 1] < num <= lis[T] 을 만족하는 곳으로, lis[T] = num으로 갱신시켜주면 된다.

3. 끝까지 진행했을 때, 최종 lis의 길이가 arr 배열의 LIS 길이이다.

 

 

정확한 흐름은 예시를 보며 다시 짚어보자.

 

위 배열의 예시를 재활용해 알아보겠다.

 

2

3

8

6

4

5

9

1

 

 

 

arr 배열의 0번째 인덱스 탐색

 

lis 배열이 비어있기 때문에 2를 lis의 마지막 위치에 추가해준다.

 

lis[0] = 2라는 의미는, 현재까지 탐색을 진행해 보았을 때 증가 부분 수열의 길이가 1이 되는 경우 중 마지막 요소의 최솟값이 2라는 의미이다.

 

 

arr 배열의 1번째 인덱스 탐색

 

lis의 마지막 요소인 2보다, 현재 탐색 중인 요소 3이 더 크기에 lis의 마지막 위치에 3을 추가해준다.

 

 

arr 배열의 2번째 인덱스 탐색

 

lis의 마지막 요소인 3보다, 현재 탐색 중인 요소 8이 더 크기에 lis의 마지막 위치에 8을 추가해준다.

 

 

arr 배열의 3번째 인덱스 탐색

 

lis의 마지막 요소인 8보다, 현재 탐색 중인 요소 6이 더 작기에 lis에 존재하는 값들 중 6이 들어갈 수 있는 위치를 이분 탐색으로 찾아 치환해주어야 한다.

치환해주는 위치는 다음 조건을 만족하는 위치이다.

 

lis[T - 1] < num <= lis[T]

 

 

lis는 자연스레 오름차순으로 정렬되어 있기 때문에 이분 탐색이 가능한 점을 이용한다.

 

위 조건을 만족하는 인덱스 번호 T는 2이므로, lis[2]의 값을 6으로 갱신시킨다.

 

arr 배열의 3번째 인덱스 값 6이 들어갈 위치를 이분 탐색으로 찾아, 기존 값에서 치환

 

갱신된 lis[2]가 뜻하는 의미는 증가 부분 수열의 길이가 3일 때 마지막 원소 값의 최솟값은 6이라는 의미이다.

 

 

arr 배열의 4번째 인덱스 탐색

 

 

lis의 마지막 요소인 6보다, 현재 탐색 중인 요소 4가 더 작기에 lis에 존재하는 값들 중 4가 들어갈 수 있는 위치를 이분 탐색으로 찾아 치환해주어야 한다.

 

arr 배열의 4번째 인덱스 값 4가 들어갈 위치를 이분 탐색으로 찾아, 기존 값에서 치환

 

lis[2] = 4 라는 의미는 위에서도 계속 언급하였듯, 증가 부분 수열의 길이가 3일 때 마지막 원소 값의 최솟값은 4라는 의미이다.

 

위와 같은 방법을 토대로 arr의 끝까지 탐색을 진행하며 lis 배열을 갱신시켜준다.

 

arr 배열의 5번째 인덱스 탐색

 

lis의 마지막 원소 4보다 현재 탐색 중인 값이 더 크므로, lis의 마지막 위치에 값을 추가해준다.

 

arr 배열의 6번째 인덱스 탐색

 

lis의 마지막 원소 5보다 현재 탐색 중인 값이 더 크므로, lis의 마지막 위치에 값을 추가해준다.

 

arr 배열의 7번째 인덱스 탐색

 

lis의 마지막 원소 9보다 현재 탐색 중인 값이 더 작으므로, 현재 탐색 중인 값 1이 들어갈 위치를 이분 탐색을 통해 찾아 치환시켜준다.

 

arr 배열의 7번째 인덱스 값 1이 들어갈 위치를 이분 탐색으로 찾아, 기존 값에서 치환

 

 

arr 배열의 마지막까지 탐색을 완료하였으므로, 최종 lis 배열의 구성 요소들은 다음과 같다.

 

LIS 알고리즘 로직 종료

 

 

위 lis 배열의 각 요소가 내포하는 의미는 다음과 같다.

 

• lis[0] = 1 : 증가 부분 수열의 길이가 1일 때 마지막 원소 값의 최솟값은 1이라는 의미
• lis[1] = 3 : 증가 부분 수열의 길이가 2일 때 마지막 원소 값의 최솟값은 3이라는 의미
• lis[2] = 4 : 증가 부분 수열의 길이가 3일 때 마지막 원소 값의 최솟값은 4라는 의미
• lis[3] = 5 : 증가 부분 수열의 길이가 4일 때 마지막 원소 값의 최솟값은 5라는 의미
• lis[4] = 9 : 증가 부분 수열의 길이가 5일 때 마지막 원소 값의 최솟값은 9라는 의미

 

따라서, 전체 배열 arr에 대한 LIS의 길이는, lis 배열의 길이인 5 이다.

 

 

시간복잡도

 

이분 탐색을 활용한 LIS 알고리즘의 시간 복잡도는 모든 배열의 요소를 순차적으로 탐색하고( O(N) ), 각 요소를 탐색할 때  기존 lis 배열의 일부를 탐색 중인 값으로 치환해야 한다면 치환할 위치를 이분 탐색을 통해 찾아야 하기에( O(lg N) ) 시간복잡도는 O(N lg N) 이다.

 

---

응용 문제

실제 LIS 알고리즘을 적용해야 하는 문제를 풀어보는 것이 도움이 될 것이다.

 

DP를 활용한 LIS 알고리즘 적용 문제 중 LIS의 길이를 도출해내는 문제는 백준 1965번 - 상자넣기 를 추천하며,

LIS의 구성 요소까지 도출해내는 문제는 백준 14002번 - 가장 긴 증가하는 부분 수열 4 문제를 추천한다.

 

입력 데이터 개수가 많아 DP를 활용하지 못하는 문제는 이분 탐색을 활용해야 한다.

이분 탐색을 활용한 LIS 알고리즘 적용 문제는 백준 12015번 - 가장 긴 증가하는 부분 수열 2 문제를 추천한다.

 

---

문제

by DP (LIS 길이 도출)

문제 링크 : 백준 1965번 - 상자넣기

1965번: 상자넣기

 

전체 코드

# 1965


def solution() -> int:
    # 현재 박스의 조합을 담을 배열
    # 모든 값을 1로 초기화
    dp = [1 for _ in range(n)]
	
    # 모든 상자의 경우를 탐색
    for idx_1 in range(n):
    	# 현재 탐색 중인 상자의 이전 상자까지의 dp 값을 확인
        for idx_2 in range(idx_1):
        	# 조건에 만족하는 이전 dp 값들 중, 가장 큰 값에 1을 더한 값을 dp의 현재 탐색 인덱스 위치에 삽입
            if box[idx_2] < box[idx_1]:
                dp[idx_1] = max(dp[idx_1], dp[idx_2] + 1)
        

    return max(dp)


if __name__ == "__main__":
    n = int(input())

    box = list(map(int, input().split()))

    print(solution())

 

 

---

 

문제

by DP (LIS 길이, 요소 도출)

문제 링크 : 백준 14002번 - 가장 긴 증가하는 부분 수열 4

14002번: 가장 긴 증가하는 부분 수열 4

 

 

 

전체 코드

# 14002

def solution():
    # dp를 2차원 배열로 선언.
    # 각 요소의 초기값은 => [ 1 , [A 배열의 각 인덱스 요소] ]
    dp = [ [1, [num]] for num in A ]

    # 모든 A배열 각 요소가 가장 마지막 요소인 경우를 탐색
    for idx_1 in range(N):
        # 조건에 만족하는 이전 dp 값들 중, 
        # 가장 큰 길이에 1을 더한 값을 해당 dp 인덱스의 0번째 인덱스 위치에 값 갱신
        # 가장 큰 길이일 때의 LIS 구성 요소에 현재 탐색 중인 수를 append한 배열을 헤당 dp 인덱스의 1번째 인덱스 위치 값으로 갱신
        for idx_2 in range(idx_1):
            if A[idx_2] < A[idx_1]:
                if dp[idx_1][0] < dp[idx_2][0] + 1:
                    dp[idx_1][0] = dp[idx_2][0] + 1
                    dp[idx_1][1] = dp[idx_2][1][:]
                    dp[idx_1][1].append(A[idx_1])
    
    max_len = 0
    result = []
    for i in range(N):
        if dp[i][0] > max_len:
            max_len = dp[i][0]
            result = dp[i][1][:]
    
    print(max_len)
    for re in result:
        print(re, end=" ")

if __name__ == "__main__":
    N = int(input())

    A = list(map(int, input().split()))

    solution()

 

 

---

문제

by 이분 탐색 

문제 링크 : 백준 12015번 - 가장 긴 증가하는 부분 수열 2

12015번: 가장 긴 증가하는 부분 수열 2

 

 

입력 데이터 개수가 최대 100만개(10^6)이고 시간 제한이 1초이므로 DP를 활용해서 풀면 시간 초과를 면치 못한다.

이럴 경우 이분 탐색을 활용해야 한다.

 

전체 코드

# 12015

def binary_search(lis, start, end, target):
    # lis[T - 1] < target <= lis[T] 위치를 만족하는 인덱스 T를 찾아야 한다. 그 위치가 치환할 수 있는 위치 change_idx
    while start < end: 
        mid = (start + end) // 2
        if target > lis[mid]:
            start = mid + 1
        else:
            end = mid
    
    change_idx = end

    return change_idx

def solution():
    lis = []
    lis_len = 0

    for idx in range(N):
        if not lis or lis[-1] < A[idx]:
            lis.append(A[idx])
            lis_len += 1
        else:
            change_idx = binary_search(lis, 0, lis_len, A[idx])
            lis[change_idx] = A[idx]
    
    print(len(lis))
            
            

if __name__ == "__main__":
    N = int(input())

    A = list(map(int, input().split()))

    solution()

 

---

풀이 후기

 

LIS 알고리즘을 모두 알아두면 여러 응용 문제를 풀 수 있어 알아두면 유용하다고 생각한다.

심지어 골드 문제도 많아서 경험치 쌓기도 좋다!