LIS(가장 긴 증가하는 부분 수열)

LIS(Longest Increasing Subsequence) 

---

수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제이다.

이 문제를 푸는 두 가지 방법이 존재한다.

 

1. Dynamic Programming (동적 계획법)

2. Binary Search (이분 탐색)

 

두가지 방법 모두 알아야하는 이유는 DP는 O(n^2)의 시간복잡도를 가지고 이분탐색은 O(nlogn)을 가지기 때문에 두 방법 모두 익혀야한다.

 

본인도 dp 방법만 익히고 이분 탐색 방법을 공부하지 않아 시간초과 이유로 공부할 겸 기록을 남긴다.

 

Dynamic Programming (동적 계획법)을 활용한 문제 풀이

가장 긴 증가하는 부분 수열

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

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

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

# d에는 i번째 가장 긴 부분수열의 길이를 넣을것이다.
d = [0 for _ in range(1001)]

for i in range(n):
    for j in range(i):
        # arr[i]가 arr[j] 크면 즉 이전보다 크고
        # i번째 가장 긴 부분수열의 길이가 j번째 가장 긴 부분수열의 길이보다 작다면
        if arr[i] > arr[j] and d[i] < d[j]:
        	# d[i]는 d[j]와 같아진다
            d[i] = d[j]
    # 길이 1 증가
    # 자기보다 큰게 없더라도 자기 자신 1이 있으므로
    d[i] += 1
print(max(d))

위 문제는 dp를 이용하여 문제를 풀었다.

 

Binary Search (이분 탐색)을 활용한 문제 풀이

가장 긴 증가하는 부분 수열2

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

위에 가장 큰 증가하는 부분 수열과 문제자체는 같은 문제이나 위에 문제는 n <= 1000 이였고 이번 문제는 n <= 1000000이다. 그래서 dp를 활용한 방식으로 문제를 풀면 시간초과가 나온다.

 

처음에는 여기서부터 아예 막혀서 찾아보다가 이분탐색을 활용한 풀이법을 알게 되었다.

 

이 풀이의 아이디어는 'd[i]를 계산하기 위해서 arr[0] ~ arr[i-1]을 다 볼 필요가 없다' 였다.

 

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

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

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

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

import bisect

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

d = [arr[0]]

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

print(len(d))

bisect에 대한 간단한 설명

 

bisect_left(literable, value) : 왼쪽 인덱스를 구하기

bisect_right(literable, value) : 오른쪽 인덱스를 구하기

 

예시

from bisect import bisect_left, bisect_right

nums = [0,1,2,3,4,5,6,7,8,9]
n = 5

print(bisect_left(nums, n))
print(bisect_right(nums, n))

'''
결과값
5
6
'''

위 풀이를 사용하면 시간 복잡도가 O(nlogn)이 걸린다.