최장 증가 부분 수열 (Longest Increasing Subsequence)
- 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라 한다
- 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 }
- 일반적으로 최장 증가 부분 수여르이 길이를 구하는 방법은 DP를 이용하는 것
import java.util.Scanner;
public class LIS_DP1 {
static int N;
static int[] arr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
// 각 위치에서의 LIS를 저장할 1차원 dp 테이블을 정의한다.
int[] dp = new int[N];
// 최대 LIS의 값.
int max = 1;
// 첫 번째 원소부터 N번째 원소까지 dp 테이블의 값을 채워 나간다.
for (int i = 0; i < N; i++) {
// 우선 해당 위치를 본인의 길이(1)로 초기화한다.
dp[i] = 1;
// 현재 원소의 위치에 대하여, 앞의 원소의 값을 비교하며 값을 갱신한다.
for (int j = 0; j < i; j++) {
// 만일 부분 수열이 증가할 가능성이 있다면
if (arr[j] < arr[i]) {
// dp 테이블에 저장된 LIS를 바탕으로 가장 큰 값을 dp[i]의 값으로 갱신한다.
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 전체 수열에서 LIS의 값을 갱신한다.
max = Math.max(max, dp[i]);
}
System.out.println(max);
sc.close();
}
}위의 코드로 구현하게되면 시간복잡도가 O(N²) 이 되는데 이를 이분탐색을 활용하여 구햔하게 되면 O(NlogN) 의 시간복잡도로 구현할 수 있게 된다
- LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴본다
- 해당 숫자가 들어갈 위치를 이분탐색으로 탐색해 삽입
import java.util.Scanner;
public class LIS_DP2 {
static int N;
static int[] arr, dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
// dp에 실질적으로 저장된 원소의 길이 = LIS인 1차원 dp테이블을 만든다.
// 해당 dp에 저장된 원소(0이 아닌 값)들은 이후 조사하는 원소들이 부분 수열을 늘릴 수 있을지에 대한 정보를 제공한다.
dp = new int[N];
// 처음에 저장된 원소는 없으므로, LIS = 0이다.
int LIS = 0;
// 첫 번째 원소부터 N번째 원소까지 dp 테이블의 값을 채워 나간다.
for (int i = 0; i < N; i++) {
// 이분 탐색을 활용하여 dp테이블에 저장된 원소를 탐색하며 현재 선택된 숫자가 dp테이블의 어떤 위치에 포함될지 파악한다.
int idx = BinarySearch(arr[i], 0, LIS, LIS + 1);
// 찾지 못한 경우
if(idx == -1) {
// 가장 마지막 위치에 원소를 삽입하고 LIS의 길이를 늘린다.
dp[LIS++] = arr[i];
}
// 찾은 경우
else {
// 해당 위치에 현재 값을 삽입하여 갱신한다.
dp[idx] = arr[i];
}
}
// LIS의 길이를 출력한다.
System.out.println(LIS);
sc.close();
}
private static int BinarySearch(int num, int start, int end, int size) {
int res = 0;
while (start <= end) {
// 중앙 값을 찾는다.
int mid = (start + end) / 2;
// 만일 현재 선택된 원소가 해당 원소보다 작거나 같다면, 앞 부분을 탐색한다.
if (num <= dp[mid]) {
// 해당 원소의 위치를 기억해둔다.
res = mid;
end = mid - 1;
}
// 만일 현재 선택된 원소가 해당 원소보다 크다면, 뒷 부분을 탐색한다.
else {
start = mid + 1;
}
}
// dp테이블에서 삽입될 위치를 찾지 못한 경우(즉, 모든 수들보다 큰 경우).
if (start == size) {
return -1;
}
// dp테이블에서 삽입될 위치를 찾은 경우.
else {
return res;
}
}
}- 해당 방법을 이용하면 최장 증가 부분 수열의 길이는 확실하게 알 수 있지만, 새로 만들어진 배열이 무조건 LIS 가 만들어지는 것은 아니라서 추가적인 작업을 해줘야 한다
출처
New, Strange, Want to try