[Algorithm] 최장 증가 부분 수열, LIS

HyunDong Lee·2022년 5월 16일
1

Algorithm

목록 보기
9/10
post-thumbnail

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];
        }
	}

0개의 댓글