최장 증가 부분 수열(LIS, Longest Increasing Subsequence)이라는 개념은 알고리즘을 조금 풀다보면 금방 접할 수 있는 개념이다.
그림의 파란색 부분처럼 LIS 배열을 만들고, 더 유리한 값으로 LIS 배열을 갱신해가는 것이다.
더 유리한 값이란 LIS 배열 내에서 기존의 순서와 동일할 때, 더 작은 값을 채택하는 것이다.
그래야 후에 더 많은 값을 추가할 가능성이 높아지기 때문이다.
하지만~,,,
이건 DP 문제집에 포함된 문제다!
그래서 DP 방식으로 풀어야 한다~...
1. DP 배열 정의
정석적인 방식대로라면, 아마도 DP[i]는 i번 인덱스까지 고려했을 때의, DP배열의 최장 길이가 될 것이다.
즉, DP[i]는 arr[i]를 마지막 원소로 하는 최장 길이 부분 수열의 길이다.
그렇다면 여기서 DP[i]가 만들어지는 규칙을 발견해낼 수 있는지를 따져보면 된다.
2. DP[i]는 어떻게 만들어지는가?
arr[i]를 마지막 원소로 한다고 했다.
그렇다면 dp[i]의 값은 이전의 길이에서 한 개가 연장된 길이를 나타낼 것이고, 앞에서 arr[i]보다 작은 값을 찾을 수 있다면 가능한 것이다.
그렇다면 dp[i]를 갱신하는 방법은 dp[j] + 1 중에서 최댓값을 갱신(조건1)하면 되는 것이고, 그 때 arr[j] < arr[i]를 만족(**조건2)한다면, 그값을 사용할 수 있으므로(증가 수열이므로) 갱신해주면 되는 것이다.
그렇게 값을 이어간다면 dp배열에는 각 위치에서의 최장 길이가 기록돼 있을 것이고, 그 중에서 최댓값이 가장 긴 증가하는 부분 수열의 길이가 된다.
현재 길이만 구한 것이므로, 문제에서 요구하는 조건대로 배열을 복원할 수 있어야 한다.
우리는 조건1과 조건2를 모두 만족할 때, 이전의 인덱스를 기억하고 있다면, 다시 복원할 수 있다!
그러므로 이 방법이라면 정답을 구할 수 있다!
코드를 작성해보자~
++추가
3. 초기값 설정
내가 항상 했음에도 망각하고 있었던 게 있다..
dp는 규칙도 중요하지만, 초기값 설정도 매우 중요하다.
초기값을 잘 설정해야만, 후에 점화식대로 올바르게 값을 찾아갈 수 있다.
일단 내가 점화식을 빠트렸으니 점화식부터 적어보자,,
if arr[j] < arr[i], then dp[i] = max(dp[j] + 1) (j < i) 이렇다.
이건 조건 1과 조건 2가 모두 포함된 내용이다.
그리고 이 때 이전의 인덱스도 같이 기억을 해야한다.
굳이 나타내자면, and index[i] = j 이렇게 적을 수 있지 않을까,,
일단 dp[0] = 1로 먼저 채워놓으면 될 거 같다.
그런 다음에 index[i] = -1로 저장해서, 끝값이라는 것을 알아차리게 하면 되지 않을까?
음 그리고 그런 논리라면, 모든 위치에 값을 채워야 할 거 같다.
왜냐면 i의 위치가 시작점일지 아닐지 알 수가 없기 때문에 우선은 dp[i] = 1과 index[i] = -1로 모두 초기화를 한 후에 연장이 가능하다면 그 때 갱신해주면 될 것이다!
정답
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// n 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 배열 입력 받기
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 배열 생성
int[] dp = new int[n];
int[] index = new int[n];
// 초기값 설정
for (int i = 0; i < n; i++) {
// 최소 길이는 1
dp[i] = 1;
// 수열의 시작점 or 중간점 or 종점일지 알 수 없음 && -1: 수열의 시작을 의미
index[i] = -1;
}
// dp
for (int i = 1; i < n; i++) {
dp[i] = 1;
index[i] = -1;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
index[i] = j;
}
}
}
// 최장 길이 찾기
int maxLength = 1;
int maxLengthIndex = 0;
for (int i = 0; i < n; i++) {
if (maxLength < dp[i]) {
maxLength = dp[i];
maxLengthIndex = i;
}
}
// 최장 길이 수열 복원
int idx = maxLength;
int[] LIS = new int[maxLength];
int beforeIndex = maxLengthIndex; // 직관적 이해를 위해 변수 생성
while (beforeIndex != -1) {
LIS[--idx] = arr[beforeIndex];
beforeIndex = index[beforeIndex];
}
// 출력
System.out.println(maxLength);
for (int i = 0; i < maxLength; i++) {
System.out.print(LIS[i] + " ");
}
}
}