LIS(Longest Increasing Subsequence) 알고리즘

LIS 란?

- N개 원소가 있는 배열에서 일부 원소를 골라내고 골라낸 원소가 이전 원소보다 큰 원소를 만족하는 부분 수열중 가장 긴 수

- 예를들어 {5, 3, 2, 6, 1, 7, 8, 9, 0} 이 원소 중에서 일부를 골라내어 전 원소보다 큰 조건을 만족하는 가장 긴 경우는 

{2, 6, 7, 8, 9} 이다. 

 

이렇게 LIS를 구할 수 있는 방법은 두가지가 있다.

1) DP( Dinymic Programmin)

2) Binary Search

 

DP로 푸는 경우

//배열을 순회
for (int k = 0; k < n; k++){
	//len 배열 각 인덱스에 최대 부분집합 길이값을 담아준다.
    len[k] = 1;//최소 길이인 1을 부여
    
    //0번째 원소에서 k번 이전 원소까지 순회  
    for (int i = 0; i < k; i++){
    
    	//만약 i번째 원소가 k번째 원소보다 작은경우 
        if(arr[i] < arr[k]){
        	
        	//i번째 원소를 k번째 원소 직전 원소로 생각하는경우
            //i번째 원소 최대 길이 + 1 => len[i] + 1
            
            //i번째 원소를 k번째 원소 직전 원소로 생각 안하는 경우
            //맨 처음에 최소 길이를 부여한 1
            
            위의 두가지 경우중에서 큰 값을 배열에 담아준다.
            len[k] = max(len[k], len[i] + 1);
        }
    }
}

//위에서 다음 len 배열에서 최대값이 최장길이부분수열 길이다.

DP로 풀면 이중 for문으로 시간복잡도O( n^2)이 된다.

 

바이너리 서치로 푸는 경우

static int binary_search(int[] lis, int left, int right, int target) {
  int mid;

  while (left < right) {
    mid = (left + right) / 2;

    if(lis[mid] < target) {
      left = mid + 1;
    }
    else {
      right = mid;
    }
  }

  return right;
}

static int lis_dp(int[] lis, int[] arr, int N) {
  //lis 배열에 arr 각 원소의 크기에 알맞은 자리에 넣어줄거다.
  lis[0] = arr[0];//맨처음에 lis 배열에 아무것도 없는경우 arr 배열 처음값 배정

  int len = 1;//arr[0]값을 넣어줬으니 lis 배열의 길이는 1이다.
  //arr 배열의 1 인덱스부터 순회 => 시간복잡도 O(n)
  for (int i = 1; i < N; i++) {
  	//lis 배열의 가장 마지막 값이 arr[i] 보다 작은경우
    if (lis[len - 1] < arr[i]) {
      lis[len++] = arr[i];//lis의 가장 마지막 값 다음 인덱스에 값을 넣어줌
    }
    //lis 배열의 가장 마지막 값이 arr[i] 보다 큰 경우 바이너리서치로 arr[i]의 위치를 찾아준다.
    else if (lis[len - 1] > arr[i]){
    
      int idx = binary_search(lis, 0, len - 1, arr[i]);//arr[i]가 lis 에 들어갈 인덱스
      lis[idx] = arr[i];
    }
  }
  return len;//lis 배열의 길이가 곧 최대길이가 됨.
}

 

arr 배열의 값들을 lis 배열에 채워 넣으면서 lis 배열의 길이가 늘어난다. 그럼 lis 배열의 가장 끝에 있는 값은 항상 제일 큰 값이다.

arr배열의 값이 lis 배열의 가장 마지막 값보다 큰 경우, lis 배열 끝에 추가해줌으로써 배열의 길이가 늘어난다.

arr배열의 값이 lis 배열의 가장 마지막 값보다 작은 경우, lis 배열의 길이는 변화가 없고 lis 값중에 하나를 대체해서 들어간다.

{5, 6, 7, 1, 8, 2, 3} 를 arr 이라고 생각하자

 arr 앞에 요소부터 lis를 만들어가면 다음과 같다.

1) arr[0] = 5 추가

{5}

2) arr[1] = 6 추가

{5, 6}

3) arr[2] = 7 추가

{5, 6, 7}

4) arr[3] = 1 추가

{1, 6, 7}

5) arr[4] = 8 추가

{1, 6, 7, 8}

6) arr[5] = 2 추가

{1, 2, 7, 8}

7) arr[6] = 3 추가

{1, 2, 3, 8}