[SW 문제해결 응용] LIS :: 최장 부분 증가 수열

LIS(Longest Increasing Subsequence)

최장 부분 증가 수열 구하는 문제

: 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제

부분 수열에 포함되는 요소들이 순서상 연속적일 필요는 없음

문제 풀이를 위한 방법으로 3가지가 있다.

1. 완전 탐색

2. 다이나믹 프로그래밍

3. 이분 탐색

완전탐색, O(2^N)

완전 검색 적용

1. 수열의 모든 부분 집합을 구하여 각 부분 집합이 증가 수열이 되는지 판별

2. 증가 수열이 되는 수열 중 가장 길이가 긴 수열을 찾음

ex)

S = {3, 2, 6, 4, 5, 1}

2^6 = 64개의 부분집합

길이가, 0일 때,  {}

1일 때, {3}, {2}, {6}, {4}, {5}, {1}

2일 때, {3,2}, {3,6}, {3,4}, {3,5}, ...

 부분 수열의 길이가 긴 것부터 조사하는 것이 유리

=> 처음으로 찾게되는 증가수열이 최장 증가수열이 될 것이기 때문

O(2^n), 지수시간복잡도

FOR i in N ->1

FOR ALL subsequence of S with length of i

IF there is one increasing subsequence

BREAK

i : 부분 수열 길이

i를 n부터 1까지 감소시키면서 반복

수열 S에서 길이가 i인 모든 부분 수열에 대해 반복

해당 부분 수열이 증가 수열인지 조사

- 증가 수열이면 반복 종료

Dynamic Programming, O(N^2)

2. 최장 증가 수열을 찾는 다른 방법

LIS(i)를 LIS(1), LIS(2), ..., LIS(i-1)와의 관계로 표현하기

1) LIS(i)가 ai를 포함하지 않는다면, LIS(i) = LIS(i-1);

2) LIS(i)가 ai를 포함한다면, LIS(i)

(1) ai가 마지막에 포함되는 최장 증가 수열 => ai 바로 전에 위치하는 요소를 찾음

(2) 증가 수열의 관계인 aj < ai 인 aj 찾기 (j < i)

(3) j값을 알 수 없으므로 i 이전에 있는 모든 j값들에 대하여 검색

(4) 그 중 최대값을 찾아 1 증가시켜 LIS(i)에 저장

LIS(i) = 1 + max(LIS(j)

j < i and aj < ai

(5) LIS 값들 중 최대값을 찾음

각 요소로 끝나는 최장 증가 수열들 중 가장 긴 수열 : 최장 증가 수열

최장 증가 수열을 구하는 문제는 각 요소로 끝나는 최장 증가 수열들을 모두 계산하면 해결된다.

DP접근 알고리즘

// LIS[i] : ai로 끝나는 최장 증가 수열의 길이 저장

FOR i in 1 -> n

LIS[i] = 1

FOR j in 1 -> i - 1

IF aj < ai AND 1 + LIS[j] > LIS[i]

LIS[i] = 1 + LIS[j]

RETURN max LIS[]

i를 수열 길이만큼 증가시키면서 반복

ai를 포함하는 증가 수열에서 ai 자신은 반드시 포함 -> 1 저장

j를 1부터 i보다 작을 때까지 증가시키면서 반복

aj가 ai보다 작고 1 + LIS[j]가 LIS[i]보다 큰 값인지 비교

크다면 LIS[i]에 LIS[j]에 1을 더한 값으로 갱신

모든 반복 종료 후 LIS[i]에 저장된 값 중 최대값 반환

두 개의 반복문 중첩, 각각 n과 n-1회 반복 -> 시간 복잡도 : O(n^2)

○ lis배열의 값 중 최댓값이 최장 부분 증가 수열

for (int i = 0; i < n; i++) {
    lis[i] = 1;
 
    // 기준점까지 증가하며 진행
    for (int j = 0; j < i; j++) {
        // 기준보다 이전 값이 크다 -> 증가 수열이 아니다.
        if (a[j] > a[i])
            continue;
 
        // 증가수열이다.
        // 이전 lis 에 1을 더한 것이 현재 lis 보다 크면 갱신한다.
        if (lis[i] < lis[j] + 1) {
            lis[i] = lis[j] + 1;
        }
    }
}

Binary Search, O(NlogN)

3. 이진 검색을 이용한 보다 효율적인 방법

1) C[k] : 길이 k의 증가 수열에 대하여 가장 작은 값을 C[k]에 저장

2) 각 위치에서 C[]를 갱신하기 위해 이진 탐색을 수행

- 수열의 요소 값을 하나씩 읽어와 C 배열의 범위를 벗어나는 값 : 마지막에 추가

- 요소 값이 C 배열의 범위 안에 포함되는 값 : 자기보다 작은 값 다음 위치에 저장

- 요소 값이 저장된 위치 : 그 요소 값으로 끝나는 최종 증가 수열의 길이

시간복잡도 : O(nlogn)

○ LIS 벡터의 길이가 최장 부분 증가 수열

vector<int> v;
vector<int> LIS;
LIS.push_back(v[0]);
for(int i=1; i<v.size(); i++){

    if(LIS.back()<v[i]) LIS.push_back(v[i]);
    else{
        auto it=lower_bound(LIS.begin(), LIS.end(), v[i]);
        *it=v[i];
    }
}