가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬

최근 들어, 알고리즘에 재미를 붙였다. 백준 문제를 풀면 문제 난이도마다 티어가 올라가는 재밌는 사이트(solved.ac)가 생겨서 뭔가 동기 부여되는 것 같다. 언어는 python을 사용하고 있다. (취준 할 때는 안 하고 꼭 뒷북치는 스타일... 그렇다고 실무에서 알고리즘이 안중 요하단 뜻은 아니다. 해야 할 때 덜 했을 뿐)

 

DP Dynamic Programming을 집중적으로 좀 보고 있는데 백준에서 신기한 문제를 마주쳤다. 가장 긴 증가하는 부분 수열 구하기이다. Longest Increasing Subsequence라고 불리기도 한다고 한다. 오늘은 LIS에 대해 작성해보았다.

 

 

가장 긴 증가하는 부분 수열

임의의 수열이 주어질 때, 수열에서 몇 개의 수를 제거하여 부분 수열을 만들 수 있다. 이때, 가장 긴 수열을 구하면 되는 문제이다. 

 

문제의 풀이 방법은 크게 두 가지이다.

1. Dynamic Programming (동적 계획법)

2. Binary Search (이분 탐색)

 

두 가지 풀이법을 모두 알아야 하는 이유는 시간 복잡도에 차이가 있기 때문이다.

 

Dynamic Programming 풀이법

백준 11053: 가장 긴 증가하는 부분 수열

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

10

20

10

30

20

50

위와 같은 수열이 주어졌을 때 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]이며 길이는 4이다.

 

x = 수열 A의 크기 

arr = 수열 A를 이루고 있는 A(i)를 담은 배열

dp = arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

 

 

# 11053번
x = int(input())

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

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

1. dp[i]의 값을 1로 초기화

2. 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없음)

3. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면 된다.

 

예를 들어 i = 4일때를 확인해보자.

i = 4 j = 0 dp[4] =1

arr[4] > arr[0] true 이므로 dp[4] = max(dp[4], dp[0] + 1) 2이다.

i = 4 j = 1 dp[4] = 2

arr[4] > arr[1] false

i = 4 j = 2 dp[4] = 2

arr[4] > arr[2] true이므로 dp[4] = max(dp[4], dp[2] + 1) 2이다.

i = 4 j = 3 dp[4] = 2

arr[4] > arr[3] false

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

4. dp배열의 원소중 가장 큰 원소를 출력한다.

정답은 4가 된다.

 

그렇다면, 이 풀이법의 시간복잡도는 어떻게 될까?

N개의 수들에 대해서 현재 위치 이전의 모든 수를 다 훑어봐야 하므로 O(N^2)의 시간복잡도를 가지게 된다.

 

Binary Search 풀이법 1

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

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

이 문제를 DP로 풀게 되면 시간 초과가 뜬다.

굳이 N개의 수들에 대해서 현재 위치 이전의 모든 수를 반복하며 훑어봐야할까? 라는 의문을 가지게 된다.

 

dp [i]를 구하기 위해 dp[0]~dp[i-1]의 최댓값을 알고 있다면 반복하지 않아도 되지 않을까? 이때 python의 bisect을 사용하면 된다.

# 12015번
import bisect

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

dp = [arr[0]]

for i in range(x):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])
        dp[idx] = arr[i]

print(len(dp))

x = 수열 A의 크기

arr = 수열 A를 이루고 있는 A(i)를 담은 배열

dp = 가장 긴 증가하는 부분 수열을 저장할 배열

 

bisect.bisect_left(arr, x): arr가 정렬되어있다는 가정하에 x값이 들어갈 위치 반환

 

1. dp를 arr[0]으로 초기화한다.

2. 현재 위치(i)가 이전 위치의 원소들보다 크면 dp에 추가한다.

3. 현재 위치(i)가 이전 위치의 원소보다 작거나 같으면, bisect.bisect_left로 이전 위치의 원소 중 가장 큰 원소의 index값을 구한다. 그리고 dp의 index 원소를 arr[i]로 바꿔준다.

 

4. dp의 길이를 출력한다.

정답은 4가 된다.

 

그렇다면, 이 풀이법의 시간복잡도는 어떻게 될까?

N개의 수들에 대해 이진 탐색을 진행하므로 O(NlogN)의 시간 복잡도를 가지게 된다.

 

Binary Search 풀이법 2

하지만, 위의 풀이대로하면 가장 긴 증가하는 부분 수열을 직접 구할 때 문제가 생긴다.

LIS의 길이뿐만 아니라 LIS 원소들을 알고 싶으면 어떻게 해야 할까?

 

[예시]

주어진 수열: 1 7 3 2 5 10 3

실제 정답: 1 2 5 or 1 2 3

1번 풀이의 결과물: 1 2 3 10

 

x = 수열 A의 크기

arr = 수열 A를 이루고 있는 A(i)를 담은 배열

dp = arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

 

수열 A의 각 원소 위치마다 가장 긴 증가하는 부분 수열의 길이를 알아내는 방식은 동일하다. 

 

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

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

14002번은 수열 A의 크기 N (1 ≤ N ≤ 1,000)이므로 DP로 풀어도 된다.

 

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

14003번: 가장 긴 증가하는 부분 수열 5

14003번은 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이므로 이분 탐색을 사용해서 풀어야 한다.

 

그 후에 해주어야 할 작업이 중요하다.

# 14002번 
x = int(input())
arr = list(map(int, input().split()))

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

max_dp = max(dp)
print(max_dp)

max_idx = dp.index(max_dp)
lis = []

while max_idx >= 0:
    if dp[max_idx] == max_dp:
        lis.append(arr[max_idx])
        max_dp -= 1
    max_idx -= 1

lis.reverse()
print(*lis)

max_dp = 가장 긴 증가하는 부분 수열의 길이

max_idx = max_dp의 위치

lis = 가장 긴 증가하는 부분 수열을 담을 배열

index	0	1	2	3	4	5	6
arr	1	7	3	2	5	10	3
dp	1	2	2	2	3	4	3

max_dp	4
max_idx	5

max_idx의 값부터 시작하여 거꾸로 순회하며 arr의 원소를 추가하면 된다.

max_dp가 4고, max_idx는 5이므로 arr[5] = 10에서부터 거꾸로 순회하면 된다. 그다음으로 올 원소는 arr[4] = 5, arr[3] = 2, arr[0] = 1이 된다. 

 

lis = [10, 5, 2, 1]이며 이걸 뒤집어서 출력하면 원하는 정답을 얻을 수 있다.

 

이렇게 LIS 푸는 방법에 대해서 작성해보았다. 여기서 풀이한 문제들 말고도 관련한 문항들이 더 있으니 해당 문제들도 도전해보면 좋을 것 같다.

 

LIS 관련 백준 문제들

11053번 11055번 11722번 12015번 12738번 14002번 14003번

 

참고 자료

나무위키: 나무위키를 그닥 믿지않는데 생각보다 설명이 잘 되어있어서 놀랐다.

유투브_ Back to Back SWE: 우연히 구글링하다가 찾았는데 설명을 되게 잘한다.

티스토리_파이리썬의 파이썬: 되게 잘 정리되어있다.