Longest Increasing Subsequence
수열
수열(數列)은 수 또는 다른 대상의 순서 있는 나열이다. 나열 순서를 생각해야 하고 중복이 허용된다는 점에서 집합과 구분된다.
부분 수열
부분 수열이란, 나열 순서가 변하지 않은 채로 일부 항을 제거해 얻는 새로운 수열을 의미한다.
최장 증가 부분 수열
부분 수열 중 오름 차순으로 정렬된 가장 긴 수열
을 최장 증가 부분 수열이라고 한다.
정의
최장 증가 부분 수열 문제는 동적 계획법
으로 풀 수 있는 유명한 알고리즘 문제이다.
예를 들어 다음과 같은 수열이 주어졌다고 하자.
5 3 7 8 6 2 9 4
위 수열에서 특정 위치에 있는 몇개의 수를 제거
해 부분 수열을 만들 수 있는데, 그 중에서 최장 증가 부분 수열을 구해보자.
✔ 첫 번째 조건은 나열 순서가 변하면 안되므로, 입력 값에 대해 오름차순 혹은 내림차순을 하면 안된다는 것이다.
✔ 두 번째 조건은 특정 위치에 있는 몇개의 수를 제거하여 만든 수열이 오름 차순이 되어야 한다는 것이다.
✔ 세 번째 조건은 그렇게 만든 부분 수열의 원소의 개수가 다른 부분 수열의 원소의 개수보다 많아야 한다는 것이다.
위 입력 예시에서 3, 6, 2, 4 를 제거하면 5, 7, 8, 9 가 되며 길이가 4인 최장 증가 부분 수열이 된다.
5, 7, 8, 9
그러면 어떠한 기준으로 제거해야하는 수를 찾을 수 있을까?
아래에서 구하고자 하는 것은 최장 증가 부분 수열의 길이
를 구하는 것이다.
첫 번째 알고리즘 : O(N^2)
첫 번째 알고리즘은 시간 복잡도가 O(N^2) 을 갖는 방식이다. 따라서 입력 N 의 범위가 2000 이 넘어가지 않는 선에서 사용 가능하다.
Step1. DP 초기화
DP 테이블을 만들고 자기 자신에 대한 개수
를 의미하는 1이라는 값으로 초기화한다.
dp = new int[N];
// dp 초기화
for (int i = 0; i < N; i++) {
dp[i] = 1;
}
Step2. next 와 prev 를 비교하며 DP 테이블 변경
인덱스는 0 부터 시작한다고 가정.
✔ dp[i]
는 i 번째 위치한 원소를 마지막으로 하는 부분 수열의 개수를 의미.
for (int i = 1; i < list.size(); i++) { // 첫 번째 인덱스 부터 시작 : next 반복문
for (int k = 0; k < i; k++) { // prev 반복문
int prev = list.get(k);
int next = list.get(i);
if(next > prev) { // 뒤에 위치한 원소의 값이, 앞에 존재하는 원소들보다 클 경우
// dp[i] 에 저장된 값이랑 dp[k] 의 값에 1을 더한 값이랑 비교하여 큰 값을 dp[i]에 초기화
dp[i] = Math.max(dp[i], dp[k] + 1);
}
}
}
Input : 5 3 7 8 6 2 9 4
1 1 1 1 1 1 1 1
Case1 : 5(1, prev) 와 3(1, next) 을 비교 -> if 문 동작 X
Case2 : 5(1,prev) 와 7(1, next) 을 비교 -> if 문 동작 O
-> dp[2] = Math.max(dp[2], dp[0] + 1)
-> dp[2] = 2;
Case3 : 3(1, prev) 와 7(2, next) 을 비교 -> if 문 동작 O
-> dp[2] = Math.max(dp[2], dp[1] + 1)
-> dp[2] = 2;
// 생략
Case3 까지 살펴봤을 때 dp[2]
는 2번째 인덱스에 위치한 7을 마지막 원소를 갖는 부분 수열의 개수를 의미한다.
따라서, 5, 3, 7 에서 부분수열은 5, 7 과 3, 7 이 가능하고 각각 최대 원소 2개를 갖기 때문에 dp[2]
에는 2가 저장되어야 한다.
구현
static void solution() {
dp = new int[list.size()];
Collections.reverse(list);
// dp 초기화
for (int i = 0; i < N; i++) {
dp[i] = 1;
}
for (int i = 1; i < list.size(); i++) {
for (int k = 0; k < i; k++) {
int prev = list.get(k);
int next = list.get(i);
if(next > prev) {
dp[i] = Math.max(dp[i], dp[k] + 1);
}
}
}
int answer = 0;
for (int i = 0; i < N; i++) {
answer = Math.max(answer, dp[i]);
}
}
두 번째 알고리즘 : O(NlogN)
두 번째 알고리즘은 이진 탐색을 활용한 기법이다. 두 번째 알고리즘은 다음과 같은 의문에서 시작한다.
dp[i] 를 계산하기 위해 Array[0] ~ Array[i - 1] 를 꼭 다 훑어봐야 하는가?
예시
3 5 7 9 2 1 4 8 수열이 있다고 가정하자.
가장 먼저 Integer.MAX_VALUE
로 DP 테이블을 초기화 한다.
그 다음, DP 의 첫번 째 원소를 초기화하고, i = 1 부터 반복문을 시작한다.
DP 에 저장된 마지막 값과 반복문을 통해서 꺼내오는 NEXT 값을 비교하여 DP 테이블에 값을 바로 저장할지, 이진 탐색을 수행하여 저장될 위치를 찾은 후에 저장할지 결정한다.
// dp 에 현재까지 갱신된 인덱스 = dp 에 마지막으로 업데이트된 인덱스
int dpIndexByLastUpdated = 0;
for (int i = 1; i < list.size(); i++) {
int next = list.get(i);
int lastValueInDp = dp[dpIndexByLastUpdated];
if(lastValueInDp < next) {
dp[++dpIndexByLastUpdated] = next;
} else {
int findIndex = binarySearch(0, dpIndexByLastUpdated, next);
dp[findIndex] = next;
}
}
위 과정을 반복한다.
i = 4일 때를 살펴보자.
Array[4] = 2이다. 이때 표의 Array[i]들을 살펴보면 2는 3보다 작은 값이다. 그러므로 DP[4] = 0 + 1 = 1이다.
표에서 DP[i] = 1일 때의 Array[i] 값은 현재는 3이나, A[5] = 2이므로 더 작은 2로 갱신해 준다. 이 말은 증가부분수열의 길이가 1인 수열 중 끝이 3으로 끝나는 증가부분수열(기존수열)과 끝이 2로 끝나는 증가부분수열(현재수열)이 있으므로, 이들 중 끝값이 더 작은 2를 X에 저장해 놓겠다는 것이다. 추후 D[i] = 2인 수열을 찾기 위해 A[5] = 2 뒤에 붙일 수 있는지만 확인하면 되기 때문이다.
DP 테이블의 최종 결과는 {1, 4, 7, 8, MAX, MAX, MAX, MAX} 가 저장되고 MAX 를 제외한 숫자가 저장된 개수를 카운트 하면 LIS 의 길이가 된다.
왜, DP 테이블에 저장된 MAX 를 제외한 숫자들의 개수가 LIS 길이가 되는지 전체 과정을 훑어보면서 이해하자.
포인트
위 과정에서 중요한 포인트는, NEXT
값이 DP[dpIndexByLastUpdated]
값보다 작다면, 최장 증가 부분 수열이 될 수 없기 때문에, 해당 값을 저장해야할 위치를 찾아서 DP 테이블을 갱신해준다는 점이다.
i가 4일때를 보면 된다. i=4 일때 Array[4] = 2 이고 DP[dpIndexByLastUpdated] = 9 이다. 따라서, 2가 삽입될 위치를 찾고 2는 부분 수열 1의 길이를 갖기 때문에 DL 에서 1의 길이를 갖는 원소와 교체해주는 것이다.
참고로, DP 저장된 값을 반복문을 통해 탐색하여 각 원소를 출력한 결과는 LIS 수열과는 전혀 상관 없다. 즉, DP 테이블에 Integer.MAX_VALUE 가 아닌 다른 값이 오름차순 형태로 저장되어있다고 해서 그 값들이 최장 증가 부분 수열이라는 것은 아니다.
구현
- ✔ dp 에 저장된 값(Integer.MAX_VALUE 를 제외한)의 개수 = LIS 의 길이
- ✔ lastValueInDp(dp 저장된 가장 마지막 값) < next(반복문을 통해 꺼내오는 값)
- ✔ dp[i] 에 next 삽입
- ✔ lastValueInDp(dp 저장된 가장 마지막 값) > next
- ✔ Binary Search 를 통해서 next 가 dp 의 어느 index 에 들어가야하는지, 알맞은 index 를 찾는다.
- ✔ dp[findIndexByBinarySearch] 에 next 삽입
public class Main {
static int N;
static int[] dp;
static List<Integer> list = new ArrayList<>();
public static void main(String[] args) {
input();
solution();
System.out.println(getAnswer());
}
static void input() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
for (int i = 0; i < N; i++) {
list.add(sc.nextInt());
}
}
static void solution() {
dp = new int[list.size()];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = list.get(0);
// dp 에 현재까지 갱신된 인덱스 = dp 에 마지막으로 업데이트된 인덱스
int dpIndexByLastUpdated = 0;
for (int i = 1; i < list.size(); i++) {
int next = list.get(i);
int lastValueInDp = dp[dpIndexByLastUpdated];
if(lastValueInDp < next) {
dp[++dpIndexByLastUpdated] = next;
} else {
int findIndex = binarySearch(0, dpIndexByLastUpdated, next);
dp[findIndex] = next;
}
}
}
/**
* 이진 탐색을 통해서 next 가 dp 의 어느 index 에 들어가야하는지, 알맞은 index 를 찾는다.
* @param start 0
* @param end dpIndexByLastUpdated
* @param target 비교 대상인 다음 값(next)
*/
static int binarySearch(int start, int end, int target) {
int index = 0;
while(start <= end) {
int middle = (start + end) / 2;
if(dp[middle] >= target) {
end = middle - 1;
index = middle;
}
else{
start = middle + 1;
}
}
return index;
}
/**
* dp 에 Integer.MAX_VALUE 가 아닌 값들에 대해서 개수를 카운트한다.
*/
static int getAnswer() {
int count = 0;
for(int i = 0; i < dp.length; i++) {
if(dp[i] == Integer.MAX_VALUE) {
break;
}
count++;
}
return count;
}
}
References
'Algorithms > 기본 지식' 카테고리의 다른 글
조합(Combination) (0) | 2022.01.03 |
---|---|
부분 집합 구하기(DFS) (0) | 2022.01.03 |
깊이 우선 탐색(DFS) (0) | 2022.01.03 |
위상 정렬 (0) | 2021.12.14 |
신장 트리와 크루스칼 알고리즘 (0) | 2021.12.13 |