[알고리즘][동적계획법] 최장 증가 부분 수열

1. 최장 증가 부분 수열

문제 정의

원소가 n개인 배열의 일부 원소를 골라내어 만든 부분 수열 중에서, 각 원소가 이전 원소보다 크다는 조건을 만족하면서 그 길이가 최대인 것을 최장 증가 부분 수열(longest increasing subsequence)이라 합니다.

 

문제 예시

다음과 같은 정수형 배열이 있다고 가정합니다.

[6, 2, 5, 1, 7, 4, 8, 3]

 

length(k)를 위치 k에서 끝나는 최장 증가 부분 수열의 길이라고 가정합니다. 그러면 0<= k <= n-1를 만족하는 모든 k에 대해서 length(k)를 계산하여 최장 증가 부분 수열의 길이를 구할 수 있습니다.

length(0) = 1 (6)
length(1) = 1 (2)
length(2) = 2 (2 -> 5)
length(3) = 1 (1)
length(4) = 3 (2 -> 5 -> 7)
length(5) = 2 (1 -> 4)
length(6) = 4 (2 -> 5 -> 7 -> 8)
length(7) = 2 (1 -> 3)

위 결과에서 최장 증가 부분 수열을 가진 결과는 6번째로써 [2, 5, 7, 8]임을 알 수 있습니다.

 

소스코드

class LongestIncreasingSubsequence {
    // array 정수 배열에서 최장 증가 부분 수열이 되는 인덱스 k를 구하시오
    // O(n^2)
    public int solution(int[] array){
        int n = array.length;
        int[] length = new int[n];
        for(int k = 0; k < n; k++){
            length[k] = 1;
            for(int i = 0; i < k; i++){
                if(array[i] < array[k]){
                    length[k] = Math.max(length[k], length[i] + 1);
                }
            }
        }

        return getIdxByMaxValue(length);
    }

    private int getIdxByMaxValue(int[] arr){
        int maxIdx = 0;
        int maxValue = arr[0];
        for(int i = 1; i < arr.length; i++){
            if(arr[i] > maxValue){
                maxIdx = i;
                maxValue = arr[i];
            }
        }
        return maxIdx;
    }
}

• length(k)의 조건 : k번째 값은 이전의 값들보다 커야함
• length(k) = length(i) + 1 : i에서 끝나는 최장 증가 부분 수열의 마지막에 array[k]를 추가하는 것을 의미함
• 시간복잡도 : O(n^2)

 

References

source code : https://github.com/yonghwankim-dev/algorithm_training/tree/main/src/main/java/kr/yh/chap06_dp/lis
알고리즘 트레이닝