26. Longest Increasing Subsequence [11-2주차]
2024년
1월 14일 일요일
오전 3:14
<Longest Increasing Subsequence>
실수 배열이 입력되었을 때, 증가하는 최장 부분
수열을 찾는 문제이다.
LCS문제에서와 마찬가지로 부분수열이란, 전체 배열에서 일부 원소를 삭제한 뒤, 남은 원소들을 순서대로 배열한
것이다.
이 문제에서는 값들이 단조 증가하는
최장 부분 수열을 찾아야 한다.
ex) 1 3 0 4 5 14 6 7 9 9 11
-> 1 3 4 5 6 7 9 11
일단은 최장 증가 부분 수열 자체가 아닌, 수열의
크기를 구할 것이다.
먼저 O(n2)알고리즘을 살펴본
뒤, O(nlogn)알고리즘을 배우자.
<Longest Increasing Subsequence - O(n2)
>
O(n2) 시간에 LIS의 길이를 구해 보자.
ms를 다음과 같이 정의한다.
ms(i)는 마지막 값이
A[i]인 최장 증가 부분 수열이다.
ex) A = {1, 2, 10, 4, 5, 7}
ms(4) = {1, 2,
4, 5}
입력 배열 A와 같은 크기의 배열 dp를 선언한다.
dp[i]에 ms(i)의
크기를 저장할 것이다.
ms(i)는 마지막 원소를 제외하면 A[i]보다 작은 수들로 구성된다.
따라서 ms(i)를 구하기 위해서는 A[i]보다 작은 수들만 고려하면 된다.
dp[i]를 계산하는 과정은 다음과 같다.
- 0 <= k < i
- dp[k]를
미리 계산해 놓는다.
- A[k] >= A[i] 라면, dp[k]를 무시한다.
- A[k] < A[i] 를
만족하는 k에 대해, dp[k]값 중 가장 큰 값을 M이라 하자
- dp[i] 에 M+1을 저장한다.
이를 통해 O(n2) 시간에
문제를 풀 수 있다.
<dp 최적화>
Dynamic Programming에서 저장된
데이터의 패턴을 보고, DP를 더욱 최적화할 수 있다.
최장 증가 부분 수열(LIS)문제에서, 부분 문제의 답인 ms(i)가 어떻게 구성되는지를 분석하여, O(nlogn)시간에 LIS를 구하는 알고리즘을 찾을 것이다.
<Longest Increasing Subsequence -
O(nlogn) >
LIS(A[]) {
dpl[];
dpl[0] = A[0];
for (loop=0; loop<n; loop++) {
A[i]를 dpl에서
binary search;
// binary search 결과, dpl[k-1] < A[i]
<= dpl[k] 이라면
dpl[k] = A[i];
}
return dpl.length - 1;
}
배열 dpl의 인덱스 i에 ms(0~n)중 길이가 i인
것의 마지막 값을 저장할 것이다.
단, 길이가 같은 ms는 마지막 값이 작은 것만 저장된다.
알고리즘은 반복문용 변수 loop를 0부터 n-1까지 증가시키며,
A[loop]값을 dpl배열의 어디에 저장할지를 판단한다.
다음 그림을 통해 알고리즘이 어떻게 동작하는지를 알아보자.
먼저, A[0]이 dpl[1]에
저장된다.
다음으로, A[1] = 8이 dpl에 들어갈 위치를 이진 탐색을 통해 찾는다.
0오른쪽에 8이
저장되게 된다.
4가 저장될 위치를 이진 탐색을 통해 찾는다.
4는 0과 8 사이에 와야 하는데, 4보다 더 큰 수, 8을 지우고 그 자리에 4를 대신 넣는다.
나머지도 마찬가지로 작동한다.
알고리즘이 끝나면, dpl에 저장된 수의 개수, 즉 dpl의 마지막 인덱스가 최장 증가 부분 수열 (LIS)의 크기가 된다.
<ms의 성질>
위 알고리즘을 증명하기 위해서, 먼저 ms에 대한 다음 성질을 증명해야 한다.
위 표는 입력 배열 A의 각 값 아래에, 해당하는 ms를 적은 것이다.
표에서 길이가 3인 ms의 마지막 값을 빨간색으로 표시했다.
그 값들을 살펴보면,
12->10->6->5 로 점점 더 작아진다는 것을 알 수 있다.
이러한 패턴이 항상 성립한다는 것을 증명해 보자.
ms(i) = {0, 4, 12}, ms(j) = {0, 2, 6} 이라 하면, 무조건 i<j, 12 뒤에
6이 나온다.
만약 i>j 로 6이 12보다 먼저 나온다면,
ms(i)로 {0, 2, 6, 12}가 더 나은 답이 되어 모순이 발생하기 때문이다.
이를 일반화하면 다음이 성립한다.
ms(i)와 ms(j)의
크기가 같고,
ms(i) 의 마지막 값보다
ms(j) 의 마지막 값이 더 작다면,
A[i]가 A[j]보다
앞에 있다.
<loop invariant를 통한 증명>
반복문의 변수 loop가 0에서 n-1까지 진행되는 동안, 다음 invariant가 유지된다.
Invariant
for루프의 변수 loop의
값이 현재 t라 하자.
루프가 끝나기 직전
1.
0<= i <= t 인 i에 대해, ms(i) 의 길이가
L이라면, ms(i)의 마지막 값은 dpl[L]에
저장되어 있다.
2.
단, ms(0~t)중 길이가 L인 것이 여러 개라면, 마지막 값들 중 가장 작은 것만이 dpl[L]에 저장된다.
3.
dpl 배열은 단조
증가한다.
이진 탐색 결과에 따라 dpl배열에 값을 저장하므로, invariant 3번이 유지됨을 알 수 있다. 1번과 2번도 증명해 보자.
loop = t가 끝나기 직전 invariant가 유지되었고, dpl에서 값이 저장된 마지막 인덱스가 L'이라 한다.
loop = t+1에서
case1) A[t+1]이 dpl[L']보다 클 경우
dpl[L']에 A[m]이 저장되어 있다고 하자.
ms(t+1)은 ms(m)의 끝에 A[t+1]을 추가한 것이고, 길이는 L'+1이다.
- 증명 : 만약 ms(t+1)의 길이가 L'+1보다 크다면, ms(t+1)의 마지막 값을 제거한 길이 L'+1이상의
배열이 ms(0~t)중에 있을 것이고, dpl의
마지막 인덱스가 L'이라는 것에 모순이 생긴다.
- dpl[L'] < A[t+1]이므로, ms(m)끝에 A[t+1]을 추가할 수 있음은 자명하다.
이진 탐색에
이후 dpl[L'+1]에 A[t+1]이 저장되므로, invariant 1이 유지된다.
아직까지 길이가 L'+1인 배열은 하나뿐이므로, invariant 2도 유지된다.
case2) A[t+1]이 dpl[L']이하인 경우.
ms(t+1)의 길이를 s라 하고
dpl[s]에 원래 A[k]가 저장되어 있다고 하면, 위에서 증명한 ms의 성질에 의해,
A[t+1] <= A[k]이다.
또한, dpl(s-1) 에 A[m]이 저장되어 있다고 하면
A[m] < A[t+1] 이다.
- 증명 : A[t+1]이 A[m] 이하라고 가정해 보자.
ms(m)의 끝에 A[t+1]이 추가될 수 없으므로, 다른 길이가 s-1인 ms(m')의
끝에 A[t+1]이 추가되어 ms(t+1)이 만들어질 것이다.
그런데 이렇게
되면 A[m']<A[m]이 되므로, invariant의 2번에 위배되어 모순이 발생한다.
따라서 A[t+1]은 무조건 A[m]보다 크다.
정리하면 A[m] < A[t+1] <= A[k] 가 성립하므로,
이진 탐색에
의해 dpl[s]에 A[t+1]이 저장된다.
따라서 invariant 1번이 유지된다.
A[t+1] <= A[k] 이므로, invariant 2번도
유지된다.
이로써 Invariant가 증명되었다.
loop가 끝날 때가 되면,
invariant 1번에 의해 dpl의 마지막 값의 인덱스가 LIS의 길이임이 증명된다.
최장 증가 수열의 크기 뿐만 아니라 수열 자체를 구하려면,
dpl[i]에 A[k]가 저장될 때마다 ms(k)의
끝에서 두 번째 값의 인덱스를 다른 배열 B에 저장해 두면 된다.
ms(k)의 끝에서 두 번째 값이 A[k'] 이라면, B[k]에 k'을
저장.
OneNote에서 작성되었습니다.