최장 증가 부분 수열(LIS)란?
- 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 주어진 수열에서 항상 증가하는 부분 수열 중 가장 긴 부분을 찾는 문제
ex)
입력: [10, 20, 10, 30, 20, 50]
출력: 3 (가능한 LIS: [10, 20, 30] 또는 [10, 20, 50])이 문제를 해결하는 대표적인 방법은 다음과 같음
- 동적 계획법(DP) - O(N²)
- 이분 탐색을 활용한 최적화 - O(N log N)
📌 동적 계획법(DP) - O(n²) (LIS 길이)
✅ 알고리즘 개요
- dp[i]: i번째 숫자를 마지막 원소로 하는 LIS의 길이를 저장하는 배열
- 점화식
dp[i] = max(dp[j] + 1) // (단, j < i이고 arr[j] < arr[i]인 경우)- 초기값: 모든 dp[i] = 1 (각 원소 자체로 LIS를 형성 가능)
- 결과: dp 배열에서 가장 큰 값이 최장 증가 부분 수열의 길이
- n이 최대가 1000이기 때문에 O(n²) 방법 사용 가능
package silver.silver2;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Problem11053 {
public static void main(String[] args) throws IOException {
// 입력
System.setIn(new FileInputStream("src/input.txt"));
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// LIS
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
// 배열의 최대값
System.out.println(Arrays.stream(dp).max().getAsInt());
}
}
📌 이분 탐색 활용 - O(n log n) (LIS 길이)
✅ 알고리즘 개요
- LIS를 유지하는 리스트(lis) 사용
- lis는 현재까지 찾은 증가하는 부분 수열을 저장하는 리스트
- 항상 오름차순을 유지해야 하며, 길이가 LIS의 길이
- 이분 탐색을 사용해 삽입 위치 찾기
- Collections.binarySearch() 또는 lower_bound를 사용하여 적절한 위치를 찾아 삽입 또는 교체
- 만약 새로운 원소가 현재 lis의 마지막 원소보다 크다면 추가
- 그렇지 않다면 적절한 위치의 원소를 현재 값으로 변경
Collections.binarySearch()는 중복된 값이 있을때는 사용을 못하니 lower_bound를 직접 구현하는 방법을 사용하는것이 좋음
- 이 문제는 최대 n이 100만 이기 때문에 DP를 활용한 O(n²) 방법을 사용하면 시간초과가 날것임
- O(n log n) 시간복잡도를 가진 이분 탐색을 활용해서 풀어야함!
package gold.gold2;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Problem12015 {
static List<Integer> lis = new ArrayList<>();
public static void main(String[] args) throws IOException {
// 입력
System.setIn(new FileInputStream("src/input.txt"));
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
int insertIndex = lowerBound(arr[i]);
if (insertIndex == lis.size()) { // 리스트의 끝에 추가해야한다면
lis.add(arr[i]);
} else {
lis.set(insertIndex, arr[i]); // 교체
}
}
System.out.println(lis.size());
}
private static int lowerBound(int value) {
int st = 0;
int en = lis.size();
while (st < en) {
int mid = (st + en) / 2;
if (lis.get(mid) >= value) {
en = mid;
} else {
st = mid + 1;
}
}
return st;
}
}
💡 실제 LIS 구하기
- 위에 소개한 방법들은 LIS 길이를 구하는 방법임
- 실제 LIS를 구하려면 경로 추적 기법을 사용하여 LIS를 복원
✅ 경로 추적을 활용한 LIS 복원 (O(N log N))
- LIS 길이를 구하는 과정에서 경로를 저장
- lis 배열은 LIS를 저장하는 배열 (lower_bound를 활용하여 삽입/교체)
- idx[i] 배열을 사용하여 각 원소가 LIS의 어느 위치에 들어가는지 저장
- idx[i] 배열을 활용하여 LIS의 마지막 원소부터 거꾸로 탐색하며 LIS를 복원
- 스택을 사용하여 LIS를 저장한 후, 순서를 뒤집어 출력
package platinum.platinum5;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Problem14003 {
static List<Integer> lis = new ArrayList<>();
static int[] idx;
public static void main(String[] args) throws IOException {
// 입력
System.setIn(new FileInputStream("src/input.txt"));
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
idx = new int[n];
for (int i = 0; i < n; i++) {
int insertIndex = lowerBound(arr[i]);
if (insertIndex == lis.size()) { // 리스트의 끝에 추가해야한다면
lis.add(arr[i]);
} else {
lis.set(insertIndex, arr[i]); // 교체
}
idx[i] = insertIndex; // 현재 원소가 LIS의 몇 번째 위치인지 저장
}
int len = lis.size() - 1;
StringBuilder sb = new StringBuilder();
Stack<Integer> s = new Stack<>();
// 뒤에서부터 LIS를 역추적하여 스택에 저장
for (int i = n - 1; i >= 0; i--) {
if (idx[i] == len) { // LIS의 현재 길이(len)에 해당하는 값 찾기
s.push(arr[i]); // LIS 원소 저장
len--; // 다음 원소 찾기 위해 감소
}
}
// 스택에서 꺼내며 LIS를 순서대로 출력
while (!s.isEmpty()) {
sb.append(s.pop()).append(" ");
}
System.out.println(lis.size()); // LIS 길이 출력
System.out.println(sb);
}
private static int lowerBound(int value) {
int st = 0;
int en = lis.size();
while (st < en) {
int mid = (st + en) / 2;
if (lis.get(mid) >= value) {
en = mid;
} else {
st = mid + 1;
}
}
return st;
}
}
✅ LIS를 활용한 최소 변경 횟수 구하기
- 일부 문제에서는 최소한의 변경으로 수열을 정렬해야 할 때, LIS(최장 증가 부분 수열)의 길이를 구한 후
N - LIS 길이를 계산하면 해결되는 경우가 많음- 예시 문제 유형:
- 배열을 정렬하기 위한 최소 변경 횟수
- 최소한의 원소를 제거하여 수열을 정렬하는 문제
- 연속된 숫자의 최장 부분 수열을 유지하며 최소 제거 횟수 구하기
- 백준 2631 - 줄세우기
