📌 LIS
LIS는 Longest increasing subsequence의 줄임말으로 증가하는 가장 긴 수열의 길이를 찾는 알고리즘이다.
[10, 20, 10, 30, 20, 50]의 배열에서 가장 긴 증가 수열을 구하자면 [10, 20, 10, 30, 20, 50]으로 길이는 4가 된다. 이와 같이 배열 내에 가장 긴 증가 수열을 구하는 알고리즘을 LIS라고 한다.
✔️ DP - O(N^2)
DP로 LIS를 풀기 전 점화식을 먼저 도출해야한다. DP의 점화식은 다음과 같다.
dp[i] = Max(dp[i], dp[j]+1)
해당 관계식을 살펴보자.
주황색으로 칠해진 5에서의 dpArr(최대 길이)의 값을 구한다고 생각해보자. 5의 위치 전까지 dpArr이 어찌저찌해서 만들 수 있는 최대 길이가 채워졌다고 가정해보자.
❗️붙일 값은 붙이려는 수열의 마지막 값보다 커야한다.
5를 수열에 붙이려면 붙이려는 수열의 맨 끝 값이 5보다 작아야 한다. 예컨데 inputArr[4] = 7에서 7은 5보다 크므로 5를 수열에 붙일 수 없다.
❗️위의 조건을 만족했다면 DP 배열에 값을 1 더해보자.
dpArr은 각 자리에서 만들 수 있는 최대 길이를 나타낸다. 만약 거기에 5라는 값이 추가됐다면 그 수열의 길이는 최대 길이 +1 이 된다. 이를 통해 5의 위치에서의 최대 길이를 구할 수 있다.
❗️DP를 통해 구현한 LIS
for (int i=1; i<=N; i++) {
dpArr[i] = 1;
for (int j=1; j<i; j++) {
if (inputArr[j] < inputArr[i])
dpArr[i] = max(dpArr[i], dpArr[j]+1)
}
}
✔️ 이분 탐색 - O(NlogN)
이분탐색을 사용하면 LIS 문제를 O(NlogN)으로 문제를 풀 수 있다.
DP를 구현한 방법에서 이분 탐색을 조금 응용하면 시간복잡도를 좀 더 개선할 수 있다. 이전에 DP를 통해 구현했을 땐, 각 DP 배열의 최대 값에 1을 더해 처음부터 순회를 했었는데, 그 순회하는 부분을 이분 탐색을 응용해 탐색의 범위를 줄일 수 있다.
DP와 동일하게 배열 두 개를 선언하지만 maxLength라는 변수를 통해 길이 값을 따로 저장하고 makeMaxLengthArray에는 실제 값을 추가하거나 이분 탐색을 통해 자리에 대치한다.
값이 추가되면 maxLength를 1씩 늘리고, 기존 배열(inputArr)을 순회하며 비교했을 때 MaxLengthArray 배열의 값이 더 작다면 이분 탐색을 통해 해당하는 위치의 인덱스를 찾아 값을 대치해준다.
최종적으로 누적된 maxLength의 값을 출력하면 증가 수열의 최대 길이를 구할 수 있다.
❗️구현 코드
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
int N = readInt();
int[] inputArr = new int[N];
for (int i = 0; i < N; i++) {
inputArr[i] = readInt();
}
int[] makeMaxLengthArray = new int[inputArr.length];
makeMaxLengthArray[0] = inputArr[0];
int maxLength = 1;
for (int i = 1; i < inputArr.length; i++) {
if (inputArr[i] > makeMaxLengthArray[maxLength - 1]) {
makeMaxLengthArray[maxLength++] = inputArr[i];
}
else {
int idx = Arrays.binarySearch(makeMaxLengthArray, 0, maxLength - 1, inputArr[i]);
if (idx < 0) idx = -1 * idx - 1;
makeMaxLengthArray[idx] = inputArr[i];
}
}
System.out.println(maxLength);
}
private static int readInt() throws IOException {
boolean isNegative = false;
int value = 0;
while (true) {
int input = System.in.read();
if (input == ' ' || input == '\n') {
return (isNegative) ? -1 * value
: value;
} else if (input == '-') isNegative = true;
else value = value * 10 + (input - 48);
}
}
}이분 탐색에서 인덱스 값을 구하는 과정은 Arrays에 binarySearch 메서드를 통해 구현했다.
lower_bound 메서드 구현과 동일하다고 보면 된다. (자세한 내용은 Arrays.binarySearch를 검색해보자)
❗️maxLength에 대한 makeMaxLengthArray 출력
[10, 20, 10, 30, 20, 50]
maxLength = 1
[10, 0, 0, 0, 0, 0]
maxLength = 2
[10, 20, 0, 0, 0, 0]
maxLength = 3
[10, 20, 30, 0, 0, 0]
maxLength = 4
[10, 20, 30, 50, 0, 0]
Process finished with exit code 0
댓글