가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)
부분 수열이란?
본래 수열에서 일부 숫자를 지워 만들 수 있는 수열
가장 긴 증가하는 부분 수열(LIS, Logest Increasing Subsequence)이란?
오름차순으로 증가하는 부분 수열 중에서 가장 긴(원소의 개수가 많은) 수열
풀이방법
1. Dynamic Programming (동적 계획법)
2. Binary Search (이분 탐색)O(N^2) 알고리즘 동적 계획법 DP
dp를 이용한 방법은 수열의 값을 하나씩 비교하기 때문에 시간 복잡도가 O(n^2)이다. dp를 이용하여 최장 증가 부분 수열의 길이를 찾는 과정을 살펴보자.
과정
증가 부분 수열의 길이가 1이기 때문에 먼저 아래와 같이 dp의 초기값을 1로 설정한다.
array[1]을 살펴보면 array[0]과 비교했을 때 더 크기 때문에 dp[1]에는 dp[0]+1인 2가 들어간다
다음으로 array[2]를 살며보면 array[0]과 비교했을 때 값이 동일하기 때문에 dp[2]에는 dp[2] 그대로 이다. 다음, array[1]과 비교했을 때 값이 더 작기 때문에 dp[2]의 값은 그대로 이다.
array[3]을 살펴보면 array[0]과 비교했을 때 더 크기 때문에 dp[3]은 1증가한 2를 갖는다. array[1]과 비교했을 때도 값이 더 크기 때문에 dp[3]은 dp[1]+1인 3을 갖는다. array[3]과 비교했을 때도 값이 더 크지만 dp[3]=3이고 dp[2]+1=2를 비교했을 때 dp[3]이 더 크기 때문에 값이 변하지 않는다.
이런 방식으로 마지막 인덱스까지 반복하면 아래와 같이 된다.
그렇기 때문에 최장 증가 부분 수열의 길이는 dp 배열의 최댓값이 4가 된다.
O(N log N) 알고리즘 이진 탐색(Binary Search)
이분 탐색을 이용한 방법은 모든 수열의 값을 일일히 비교하지 않아도 되기 때문에 시간 복잡도가 O(nlogn)이다. 이분 탐색으로 할 때는 x와 dp 두가지가 필요하다.
과정
dp[0]에는 1 x에는 배열의 첫번째 값을 넣어주고 시작한다.
array[1]의 값이 x배열의 마지막 값인 10보다 크기 때문에 x 배열에 array[1]을 넣어준다. dp에는 증가 부분 수열의 길이가 1증가했기 때문에 dp배열의 마지막 값에서 1 증가한 값을 넣어준다.
다음으로 array[2]를 보면 x의 마지막 값보다 작기 때문에 x 배열 어디에 들어갈 수 있을지 이분탐색을 이용해 찾는다. array[2]의 값은 x[0]에 들어갈 수 있기 때문에 x[0]을 array[2]의 값으로 바꾸어준다.
array[3]을 보면 x의 마지막 값보다 크기 때문에 x 배열의 뒤에 값을 넣어주고 dp도 마지막 값에서 1증가한 값을 넣어준다.
위 과정을 반복하면 아래와 같은 결과가 나온다.
그렇기 때문에 최장 증가 부분 수열의 길이는 4이고 수열의 값들을 x인것을 확인할 수 있다. 최장 증가 부분 수열의 길이만 알 수 있는 dp와는 달리 최장 증가 부분 수열도 찾을 수 있다.
package baekjoon_java.GoldII;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* 백준 12015번 가장 긴 증가하는 부분 수열 2 (https://www.acmicpc.net/problem/12015)
*/
public class 가장긴증가하는부분수열2 {
static int[] arr;
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int A = Integer.parseInt(br.readLine());
arr = new int[A];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < A; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
dp = new int[A];
dp[0] = arr[0];
int x = 0;
for (int i = 0; i < A; i++) {
if (arr[i] > dp[x]) {
dp[++x] = arr[i];
} else {
int targetIdx = binarySearch(x, arr[i]);
dp[targetIdx] = arr[i];
}
}
System.out.println(x + 1);
}
public static int binarySearch(int high, int target) {
int low = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (dp[mid] < target) low = mid + 1;
else high = mid - 1;
}
return low;
}
}