LIS
원소가 n개인 수열에서 부분 원소를 추출하여 만든 부분 수열 중에 원소가 오름차순으로 정렬된 수열의 길이를 LIS라고 한다.
예를 들어, 1 5 4 3 2 6 7 1 이런 수열이 있다.
위 수열의 부분 수열은
길이가 1짜리
1, 5, 4, 3, 2, 1, ...
길이 2짜리 부분 수열
1 5, 5 4, 4 3, 3 2, 2 1, ...
길이 3짜리 부분 수열
1 5 4, 5 4 3, ...
이렇게 만들 수 있어요. 그러면 여기서 증가하는 부분 수열이라 함은 오름차순으로 된 부분 수열을 나열해보자.
1 5, 1 4, 1 3, 1 2, ..., 1 3 6 7, 1 2 6 7 등이 있다.
그러면 가장 긴 수열의 길이는 4이다!
LIS w/ DP
이를 만드는 방법으로 dp를 활용할 수 있다.
왜? 부분 수열은 가장 짧은 길이가 1이다. 그러면 초기에 모든 인덱스에 해당하는 원소는 길이가 1인 배열의 형태를 가질 수 있고, 또 각각 자기 자신 이전에 자기보다 작은 값들의 갯수를 센다면 가장 긴 길이를 찾을 수 있을 것 같다.
설명이 살짝 부족한데 하나의 예시를 보자.
예를 들어,
10 12 15 17의 LIS길이를 계산한다고 가정해보자.
10부터 확인하면 10은 길이가 1인 증가하는 부분 수열이 맞다. LIS길이 = 1
이제 12를 살펴보면 12 입장에서 12보다 앞에 있는 녀석들만 확인하면 된다.
12 앞에 10이 있다 그러면 10보다 12가 크다. LIS길이 = 2
15 입장에서 확인하면 12에서 미리 계산 해놓은 LIS길이 = 2 인 것을 이용한다면 15에서 바로
LIS 길이를 3으로 갱신할 수 있다.LIS길이 = 3
이런 식으로 동적으로 앞에서 계산해 놓은 것을 가져와 확장시켜 계산을 할 수 있다 => DP
이제 아래 코드를 보면 너무 쉽게 이해할 수 있다.
int main(){
int dp[] = {1};
int arr[] //입력 받은 수열
for(int i = 0; i < N;i++){
for(int j = 0;j < i;j++){
if(arr[i] > arr[j]){
dp[i] = max(dp[i], dp[j+1]);
}
}
}
}
하지만 위 코드의 시간 복잡도는 O(N^2)이다. 너무 느리기 때문에 여기서 이분탐색 O(nlogn)의 시간 복잡도를 가지는 알고리즘을 사용하자!
LIS w/ Binary Search + DP
이분 탐색을 사용하여 LIS를 계산하는 것은 실제 LIS를 구해야 할 때이다. 예를 들어 원소가 특정 위치에 들어가야 하는 위치를 찾고 LIS 길이를 유지시킨다.
예를 들어, 다음과 같은 수열이 있을 때 LIS 배열에 삽입하면서 계산을 해보자.
arr = 10 3 2 11 9 4 5 8 20
LIS = [10]
arr = 10 3 2 11 9 4 5 8 20
LIS = [3]
arr = 10 3 2 11 9 4 5 8 20
LIS = [2]
arr = 10 3 2 11 9 4 5 8 20
LIS = [2 11]
arr = 10 3 2 11 9 4 5 8 20
LIS = [2 9]
arr = 10 3 2 11 9 4 5 8 20
LIS = [2 4]
arr = 10 3 2 11 9 4 5 8 20
LIS = [2 4 5]
arr = 10 3 2 11 9 4 5 8 20
LIS = [2 4 8]
arr = 10 3 2 11 9 4 5 8 20
LIS = [2 4 8 20]
아래 코드를 보면 이제 이해가 잘 될것 같다!
int n;
int arr[];
int LIS[];
int binarySearch(int left, int right, int target){
while(left<right){
int mid = (left+right)/2;
if(lis[mid] < target){
left = mid+1;
}
else{
right = mid;
}
}
return right;
}
int main(){
int n ;
cin >> n;
cin >> arr[];
LIS[0] = arr[0];
int idx = 0; //현재 인덱스
for(int i = 1;i < n;i++){
if(LIS[idx] < arr[i]){ //바로 뒤에 붙인다. LIS 가장 뒤보다 현재 원소가 크다면
LIS[idx+1] = arr[i];
idx++;
}
else{ //만약에 작다면 어느 포지션에 삽입할 수 있을지 위치를 찾아서 현재 원소를 삽입
int loc = binarySearch(0, idx, arr[i]);
LIS[pos] = arr[i];
}
}
