최장 증가 부분 수열(Longest Increasing Subsequence)

최장 증가 부분 수열(LIS)

 

LIS란?

 

 - 임의의 수열이 주어졌을 때 이 수열의 부분 수열 중 원소가 증가하는 부분 수열을 만든다.

    이 부분 수열 중 길이가 최장인 수열을 의미한다.

 

 - 부분 수열이란, 원래의 수열 중 임의의 원소를 삭제한 수열을 말한다.

 

 - Ex) 원래 수열 : 1 9 8 7 5 2

        부분 수열 : 1 8 7 2 / 9 5 2 / 1 5 등

        증가 부분 수열 : 1 9 / 1 8 / 1 7 등

 

 

---

 

LIS 알고리즘1 - 완전 탐색

 

 - 수열의 원소를 하나씩 탐색하며, 해당 원소가 포함이 될 지 안될 지를 선택하며 탐색한다.

 

 - 원소가 N개인 경우 시간 복잡도는 O($2^N$)가 되기 때문에 매우 비효율적이다.

 

---

 

 

LIS 알고리즘2 - DP

 

 - 수열의 원소를 하나씩 탐색하며, 해당 수열이 마지막으로 올 수 있는 경우의 최장 길이를 저장한다.

 

 - 원소가 N개인 경우 시간 복잡도는 O($N^2$)이 된다.

 

 - 앞의 원소는 해당 원소까지의 최장 길이를 미리 저장해 놓기 때문에 다시 계산하지 않는다.

 

// 원래의 수열
vector<int> arr;

int findLIS(){
	int N = arr.size();
    
    // 해당 인덱스의 원소를 마지막으로 하는 LIS 저장.
    // 기본 값은 자기 자신 하나만 선택하는 경우이기 때문에 1을 대입한다.
    vector<int> arrLIS(N,1);
    
    int result=0;
    
    for(int i=0;i<N;i++){
		// 현재 인덱스 보다 작은 원소 중 최장 길이를 찾는다.
    	for(int j=0;j<i;j++){
        
        	// arr[i] > arr[j] 
            // : 현재 인덱스의 원소보다 작은 값을 찾는다.
            //	 자신보다 큰 경우 증가 수열이 되지 않기 때문에 고려하지 않는다.
            
            // arrLIS[i] < arrLIS[j] +1 
            // : 현재 갱신된 최장 길이보다 탐색하는 인덱스의 길이 +1 인 경우 갱신해준다.
            //   탐색하는 인덱스의 원소는 현재 원소보다 작기 때문에 길이를 +1 해주어야 
            //   내가 포함되었을 때의 길이가 된다.
        	if(arr[i] > arr[j] && arrLIS[i] < arrLIS[j]+1){
            	arrLIS[i] = arrLIS[j]+1;
                
            }
        }
        
        result = max(result,arrLIS[i]);
    }
    
    return result;
}

 

 - 관련 문제

 

11055번: 가장 큰 증가 부분 수열

 

14002번: 가장 긴 증가하는 부분 수열 4

 

---

LIS 알고리즘3 - DP + 이분 탐색

 

 

 - LIS의 길이를 만족하는 최대 값을 미리 저장해 놓는다.

 

 - D[i] 는 LIS의 길이가 i인 최소 원소라고 정의하자.

   예를 들어 D[3] = 6 이라는 것은 LIS 길이3을 만족하는 마지막 원소 중 가장 작은 원소가 6이라는 것이다.

 

 - D배열를 탐색하며 D배열의 원소 > 현재 탐색 원소를 만족하는 값을 찾아서 갱신시킨다.

 

 - D배열은 그 값이 오름차순 되어 있기 때문에 값을 찾을 때 이분 탐색을 이용한다.

 

 - 시간 복잡도는 원래 배열 탐색 Nx이분탐색 이므로 O(NlogN)이다.

 

D[0] = numbers[0];

// 최장 길이 저장
int maxLength = 1;

for (int i = 1; i < N; i++) {
	int left = 0;
	int right = maxLength-1;

	// 이분 탐색으로 원소가 들어갈 위치를 찾는다.
	while (left <= right) {
		int mid = (left + right) / 2;

		if (D[mid] == numbers[i]) {
			left = mid;
			break;
		}
		else if (D[mid] > numbers[i]) {
			right = mid - 1;

		}
		else {
			left = mid + 1;
		}
	}
		
	// left는 일치한 경우 그 값을,
    // 일치하지 않는 경우 탐색 원소보다 큰 값중 가장 작은 값의 인덱스이다.
	D[left] = numbers[i];
        
    // left+1을 하는 이유는 인덱스가 0부터 시작하기 때문에
    // 인덱스 left까지의 개수는 left+1이 된다.
	maxLength = max(maxLength, left+1);
}

 

 

 - 관련 문제

 

12015번: 가장 긴 증가하는 부분 수열 2

 

12738번: 가장 긴 증가하는 부분 수열 3

 

2352번: 반도체 설계