[Algorithm/DP] 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

 

최장 증가 부분 수열이란?

 

어떤 수열이 나열되어 있을 때, 그 배열 순서를 유지하면서 점점 커지는 부분 수열의 가장 길이가 긴 수열을 구하는 문제.

 

ex)

3, 1, 5, 2, 4, 6 이라는 수열이 있을 때,

3, 1, 5, 2, 4, 6 --> [1, 2, 4, 6] 이라는 해를 구할 수 있고, 길이는 4이다.

 

 

 

 

 

---

 

접근법 + Java 코드

 

 

1. 완전 탐색

수열의 모든 부분집합을 구한 후, 길이가 긴 수열부터 그 부분집합이 증가하는 수열인지 확인한다.

이 방법은 부분집합을 전부 구하는 Brute-force 방법이기 때문에, 시간복잡도는 O(2^n)이라고 할 수 있다.

 

ex)

[3, 1, 2, 4, 5, 6] -> [3, 1, 2, 4, 5] , [3, 1, 2, 4, 6] , [3, 1, 2, 5, 6] , ..... -> 길이가 4인 수열 [1, 2, 4, 6] -> 길이가 3인 수열 -> ...

 

 

 

 

 

2. DP-1

수열을 조회하면서 현재 원소보다 작은 원소들의 LIS 중 제일 큰 값 + 1을 현재 LIS에 저장해준다. 이게 무슨말이냐...!

현재 원소가 앞에 있는 것들보다 제일 커야 하기 때문에, 자신보다 작은 것의 LIS 맨 뒤에 현재 원소를 붙인다는 뜻으로 이해하면 편하다.

 

ex)

index : 0	1	2	3	4	5
arr[i] : 3	1	5	2	4	6
LIS[i] : 1	1	2	2	3	4

index=0 : 비교할 수가 없으니까 -> LIS[0] = 1

index=1 : 1이 3보다 작으므로 3 뒤에 못선다. -> LIS[1] = 1

index=2 : 1,3 뒤에 설 수 있으므로 LIS[0]+1, LIS[1]+1 실행 -> LIS[2] = 2

index=3 : 1 뒤에 설 수 있으므로 LIS[1]+1 -> LIS[3] = 2

index=4 : 3, 1, 2 뒤에 설 수 있으므로 LIS[0]+1, LIS[1]+1, LIS[3]+1 순서대로 실행하므로 가장 큰 값+1 저장 -> LIS[4]=3

index=5 : 모든 원소 뒤에 설 수 있음. LIS[0]+1 ~ LIS[4]+1 실행 -> LIS[5]=4

 

이 방법은 LIS의 길이만 구할 수 있다. 또 시간복잡도는 반복문을 두번 도므로 O(n^2)

 

 

 

 

 

3. DP-2 Binary Search 활용

이건 2번 방법과 접근 방식이 또 다르다.

C[k] : 길이가 k인 증가 수열에 대하여 k 위치에 올 수 있는 값 중 가장 작은 값을 저장한다. << 이 개념을 사용한다.

왜 가장 작은 값을 저장하냐면 뒤에 설 수 있는 값도 앞에 다른 큰 값이 와있으면 못 서기 때문이다.. 무슨 경우냐면

3,1,5,2,4,6에서 C[1]이 3이라면 C[2]에 2가 원래 올 수 있는데 못 오는 경우를 얘기한다.. 그래서 C[1]에 1을 저장해야 하는 것이다.

 

	3	1	5	2	4	6
C[1]	3	1	1	1	1	1
C[2]			5	2	2	2
C[3]					4	4
C[4]						6
C[5]
C[6]

 

이런 식으로 현재 원소의 자리를 이진탐색으로 찾으면 끝난다. 

이진탐색의 전제 조건은 배열이 정렬되어 있어야 한다.

 

현재 원소가 앞 원소 뒤에 설 수 있는 지 없는 지 판단하고,

설 수 있으면 배열 뒤에 추가해주고 아니면 이진탐색을 통해 자리를 찾고 그 자리를 꿰찬다. 

이런 식으로 배열의 정렬을 유지해줄 수가 있다.

 

시간복잡도는 O(nlogn)

 

 

 

---

코드

 

<SWEA 3307 최장 증가 부분 수열> 문제의 자바 코드로 비교를 해보자.

 

DP-1의 방법

int[] lis = new int[n];
int answer = 0;
for (int i=0; i<n; i++) {
    lis[i] = 1;
    for (int j=0; j<=i-1; j++) {
    	// 현재 원소가 더 크고 저장된 길이보다 (앞에 있는 것 + 현재 원소)의 길이가 더 길면 
        if (arr[j] < arr[i] && lis[i] < lis[j] + 1) {
            lis[i] = lis[j] + 1;
        }
    }
}
for (int i=0; i<n; i++) {
	// 제일 큰 값 찾아서 answer에 저장
    if (answer < lis[i]) {
        answer = lis[i];
    }
}

 

 

 

DP-2의 방법

ArrayList<Integer> lis = new ArrayList<>();
lis.add(arr[0]); // 맨 앞 원소로 초기화

for (int i=1; i<n; i++) {
	// lis 맨 뒤에 있는 값보다 현재 원소가 더 크면 뒤에 추가
    if (arr[i] > lis.get(lis.size()-1)) {
        lis.add(arr[i]);
    // 그렇지 않으면 이진탐색으로 자리를 찾고 교체해준다.
    } else {
        int idx = Arrays.binarySearch(lis.toArray(), arr[i]);
        // binarySearch를 해서 그 값이 없으면 적절한 위치를 음수로 반환해주기 때문에
        // 인덱스를 양수로 처리를 해주어야 한다.
        if(idx < 0) idx = -(idx+1); 
        lis.set(idx, arr[i]);
    }
}

Arrays의 내장함수인 binarySearch를 쓰면 코드를 간단하게 짤 수 있다.

배열은 정렬되어 있다는 가정을 하고 왼쪽 인자로 넣어주고, 찾으려는 값을 오른쪽 인자에 넣어주면 된다.

값을 못찾으면 음수로 인덱스를 반환한다는 특징이 있기 때문에 처리를 또 해주어야 한다.

 

DP-1 방법보다 시간적으로 효율적인 것을 확인할 수 있다.

 

 

 

 

 

 

---

대표적인 LIS 문제

 

 

SW Expert Academy

 

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