📌 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란?
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.
예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이 됩니다.
{ 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 입니다.
일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법은 DP를 이용하는 것입니다.
아래에서 length[i] 는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미합니다.
for (int k = 0; k < n; k++){
length[k] = 1;
for (int i = 0; i < k; i++){
if(arr[i] < arr[k]){
length[k] = max(length[k], length[i] + 1);
}
}
}주어진 배열에서 인덱스를 한 칸씩(k+=1) 늘려가면서 확인합니다. 그리고 내부 반복문으로 k보다 작은 인덱스들을 하나씩 살펴 보면서 arr[i] < arr[k]인 것이 있을 경우, length[k] 를 업데이트합니다.
업데이트 하는 기준은,
(1) i번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[k]를 추가했을 때의 LIS 길이와
(2) 추가하지 않고 기존의 length[k] 값
둘 중에 더 큰 값으로 length[k] 값을 업데이트합니다.
그런데 위 알고리즘의 시간복잡도는 O(n^2) 입니다. 인풋 값이 백만 개 정도만 되어도 O(n^2)의 알고리즘은 실행시간이 10초 이상 소요된다고 알려져 있습니다.
🔍 LIS의 길이를 구하기 위해 이분탐색을 활용합니다. (이분탐색을 활용한 LIS 구하기)
시간복잡도를 개선하기 위하여 LIS를 구성할 때 이분탐색을 활용합니다.
즉, LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분탐색으로 탐색해서 넣습니다.
이분탐색은 일반적으로 시간복잡도가 O(log n) 이라고 알려져 있으므로, 이 문제의 시간 복잡도를 O(nlog n)으로 개선시킬 수 있게 됩니다.
🏅 백준 : 12738 가장 긴 증가하는 부분 수열 3
[문제]
수열 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,000,000,000 ≤ Ai ≤ 1,000,000,000)
[출력]
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
[예제 입력 1 ]
6
10 20 10 30 20 50
[예제 출력 1 ]
4
[풀이]
증가하는 부분 수열이라는 말을 보고 LIS(최장 증가 부분 수열)알고리즘이 떠올라야합니다.
LIS
배열 내에서 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그러한 부분 수열 중 길이가 가장 긴 수열을 LIS(최장 증가 부분 수열)라고 합니다.
해당 문제에서는 {10, 20, 30, 50}이 LIS입니다.
참고: https://chanhuiseok.github.io/posts/algo-49/
[문제의 이해]
해당 문제가 LIS 자체를 찾는 것이라면 조금 더 문제가 복잡해질 수 있지만 이 문제의 경우는 LIS의 길이를 물어보고 있습니다.
일반적으로 LIS의 길이를 구하는 것은 dp와 이분탐색이 있습니다. 하지만 이 문제에서는 dp로 풀 경우 시간초과가 나므로 이분탐색으로 푸는 것이 좋겠습니다.
LIS를 구성할 res에는 당연히 오름차순으로 숫자가 들어가야할 것입니다.
문제의 핵심은 LIS의 길이를 물어보고 있다는 점입니다. LIS가 엉망이어도 상관이 없습니다.
- res에 배열의 첫번째 값을 넣어줍니다.
- for문으로 배열의 끝까지 검사를 하게 되는데
2-1. res에서 가장 큰 값보다 arr[i]가 더 크다면 그대로 res에 append해줍니다.
2-2. 아니라면 res 배열에서 해당하는 숫자가 있는지 이분탐색으로 찾아보고 res[index]에 arr[i]를 넣어줍니다.
res의 길이를 출력합니다.
문제는 LIS의 길이를 묻는 것이다.
여기서 2번에서 많은 생각이 들기 시작합니다. LIS는 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 순서를 무시하면 안되는데 for문을 돌리다가 res의 최댓값보다 작은 수가 뒤에 나왔는데 res에 해당하는 숫자를 업데이트를 해주니까 말이죠.
하지만 이것은 LIS의 길이를 구하는 문제이기 때문에 상관이 없습니다.
res에 k개의 숫자가 들어가있다고 가정하면 우리는 가장 큰 res[k]만 신경쓰면 됩니다. res의 길이가 길어지기 위해선 res[k]보다 큰 수가 들어와야하니까요.
그래서 res[0]~res[k-1]까지의 숫자는 바뀌어도 정답에는 영향이 없습니다.
예를 들어 입력 값으로
7
10 20 10 30 20 5 50
을 넣게 되면 LIS는 {10, 20, 30, 50}입니다.
하지만 실제 위에 있는대로 문제를 풀게 되면 {5, 20, 30, 50}이 res에 담겨있습니다
n = int(input())
arr = list(map(int, input().split()))
res = [arr[0]]
def binary_search(start, end, target):
while start <= end:
mid = (start + end) // 2
if res[mid] == target:
return mid
elif res[mid] < target:
start = mid + 1
else:
end = mid - 1
return start
for i in range(1, n):
if res[-1] < arr[i]:
res.append(arr[i])
else:
idx = binary_search(0, len(res)-1, arr[i])
res[idx] = arr[i]
print(len(res))문제 이름은 다르지만 푸는 패턴이 완전히 동일한 문제
🏅 백준 : 2352 반도체 설계
[문제]
예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오
[입력]
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.
[출력]
첫째 줄에 최대 연결 개수를 출력한다.
6
4 2 6 3 1 5
[예제 출력 1 ]
3
[풀이]
최대 연결 개수라는 말을 보고 LIS(최장 증가 부분 수열)알고리즘이 떠올라야합니다.
import sys
input = sys.stdin.readline
'''
이게 왜 LIS 문제 ?? 최장 길이 찾는거 ? 왜??
>> 백준 2352번 문제는 주어진 포트 번호를 이용해 두 항구를 연결하는 케이블의 최댓값을 찾는 문제입니다.
두 포트 번호가 증가하는 순서대로 연결된 케이블의 수가 많아야 하는데,
이는 본질적으로 최장 증가 부분 수열을 찾는 문제와 유사합니다.
그렇다면 왜 이진탐색 문제에서 LIS 문제를 풀 때,
"bisect_left"를 사용할까?
1. 코드봐도 진짜 모르겠는데
'''
n = int(input())
arr = list(map(int, input().split()))
res = [arr[0]]
def binary_search(start, end, target):
while start <= end:
mid = (start + end) // 2
if res[mid] < target:
start = mid + 1
else:
end = mid - 1
return start
for i in range(1, n):
if res[-1] < arr[i]:
res.append(arr[i])
else:
idx = binary_search(0, len(res)-1, arr[i])
res[idx] = arr[i]
print(len(res))
''' bisect_left 적용ver
from bisect import bisect_left
res = [arr[0]]
for i in range(1, n):
if res[-1] < arr[i]:
res.append(arr[i])
else:
idx = bisect_left(res, arr[i])
res[idx] = arr[i]
print(len(res))
'''