JB의 이모저모
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} 이
www.acmicpc.net
문제
수열 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 (이분 탐색)을 활용한 문제 풀이
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
문제
수열 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)이 걸린다.
'알고리즘 > 공부' 카테고리의 다른 글
Knapsack Problem (Python) (0) | 2023.09.21 |
---|---|
진수 변환 (Python) (0) | 2023.09.14 |