[알고리즘 정리] 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)

LIS 알고리즘은 주어진 수열 내에서 가장 긴 부분 수열의 길이를 찾아내는 알고리즘입니다.

예를 들어, [3, 7, 5, 2, 6, 1, 4]라는 수열이 주어졌을 때, 증가하는 부분 수열은 [3, 5], [3, 5, 6], [1, 4] 로, 총 세 가지가 존재합니다.

LIS를 구하는 알고리즘으로는 2가지가 있으며, 두 방법 모두 동적 계획법을 사용합니다.

1. 이중 for문
2. 이분 탐색

이중 for문

먼저 이중 for문을 사용한 알고리즘을 살펴보겠습니다.

for (int i = 0; i < N; i++) {
    dp[i] = 1;

    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
            dp[i] = dp[j] + 1;
        }
    }
}

dp[i] 는 i번째 요소까지 진행했을 때의 최장 증가 부분 수열의 길이를 담고 있습니다.

Bottom-up 방식의 DP를 사용하며, 이중 for문으로 작성됩니다. 작동 과정은 다음과 같습니다.

1. i번째 요소를 기준으로 잡습니다.
2. j를 0부터 시작해 i전까지 증가시키며, 각 요소 값을 i번째 요소와 비교해, 증가하는 양상을 보이는 지 확인합니다.
3. 2에서 증가하는 부분 수열임이 확인되면, 메모된 값을 비교해 갱신합니다.

아래 예시를 통해 배열 dp의 요소들을 채워보도록 하겠습니다.

배열 [3, 7, 5, 2, 6, 1, 4]에 위 알고리즘을 적용시켜 보겠습니다. 먼저, 현재 i는 4를 가리키며, 이전까지 작업을 통해 dp 배열의 요소들이 갱신됐다고 가정하겠습니다.

먼저, 외부의 for문이 실행되어 새로운 i를 가리키면, 해당 요소를 시작으로 새롭게 증가하는 부분 수열이 만들어질 수 있기 때문에, dp[i]를 1로 초기화합니다.

j가 2를 가리키면, arr[j] < arr[i]를 만족하게 됩니다. 이는, 기존의 증가 부분수열에 i번째 요소를 붙였을 때에도 증가하는 부분 수열 [3, 5, 6]을 만족한다는 것을 의미합니다. 따라서, 이전에 만들었던 부분 수열 [3, 6]을 통해 갱신된 dp[4] 값 2를, 3으로 갱신해줍니다.

위처럼 이중 for문을 사용해 동적 계획법으로 작성하면, 시간 복잡도는 $O(N^2)$이 됩니다. 따라서, 전체 배열의 길이가 클수록, 실행 시간이 길어지게 됩니다.

이분 탐색

위에서 봤던 이중 for문 방식의 풀이는 dp 배열의 요소 dp[i]는 i번 요소까지 진행했을 때의 최장 증가 부분 수열의 최대 길이를 의미합니다.

반면, 이분 탐색을 이용한 풀이는 dp 배열을 증가하는 부분 수열의 형태를 유지합니다. 그 규칙은 다음과 같습니다.

1. 현재 요소가 dp 배열의 마지막 요소보다 크다면, 증가 형태를 만족하므로 맨 뒤에 추가한다.
2. 그 외의 경우는, 이미 작성된 dp 배열에 알맞은 위치로 찾아 들어간다.

위의 2번 규칙에서 알맞은 위치를 찾는 과정에 이분 탐색이 사용됩니다.

int idx = 0;
dp[0] = arr[0];

for (int i = 1; i < N; i++) {
    if(dp[idx] < arr[i]) {
            dp[++idx] = arr[i];
    } else {
            int targetIdx = binarySearch(idx, arr[i]);
            dp[targetIdx] = arr[i];
    }
}

int binarySearch(int high, int target) {
    int low = 0;

    while (low <= high) {
            int mid = (low + high) / 2;

            if(dp[mid] < target) low = mid + 1;
            else high = mid - 1;
    }

    return low;
}

코드는 위와 같습니다. idx는 매 단계에서 dp배열에 작성된 마지막 요소를 가리키고 있게 됩니다. 따라서, 최장 증가 부분 수열의 길이는 idx+1 이 됩니다.

위 방법으로 작성된 코드는 이분 탐색을 이용하므로, $O(nlogn)$의 시간 복잡도를 갖습니다.

수열 {10, 20, 10, 30, 20, 50}의 LIS 길이 구해보기

예를 들어, 위 A 수열이 주어졌을 때 최장 증가 부분 수열을 구하는 과정을 살펴보겠습니다. 먼저 dp[0]은 A[0]으로 초기화합니다. 이제 인덱스 i를 1부터 5까지 순회하며, A[i]를 증가 부분 수열에 포함시키는 작업을 수행합니다.

A[i] > dp[idx] 이므로, idx를 1 증가시킨 곳에 A[i]를 추가해줍니다.

A[i] ≤ dp[idx] 이므로, 이전에 작성된 요소를 덮어 씌우기 위해 targetIdx를 찾습니다. 이분 탐색을 통해 리턴된 인덱스 0에 A[i]를 덮어 씌웁니다. idx는 여전히 1을 가리키고 있습니다.

A[i] > dp[idx] 이므로, idx를 1 증가시킨 곳에 추가해줍니다.

A[i] ≤ dp[idx] 이므로, 이분 탐색을 통해 targetIdx 1을 얻습니다. 이 자리에 A[i]를 덮어 씌웁니다. idx는 여전히 2를 가리키고 있습니다.

A[i] > dp[idx] 이므로, idx를 1 증가시킨 곳에 추가해줍니다. 순회가 끝난 시점에서 idx는 3을 가리키고, 이는 증가 부분 수열을 의미하는 배열 dp에 추가된 요소의 개수가 3+1개라는 것을 의미합니다. 따라서, 이 경우 최장 증가 부분 수열의 길이는 4가 됩니다.

LIS 자체를 구하는 방법

위 이분 탐색 방법에 추가로 역추적을 방법을 사용합니다. 아이디어는 다음과 같습니다. 역추적을 위한 새로운 배열 tracking이 사용됩니다.

1. 요소를 배열 dp에 추가하는 작업 외에, 추가한 위치 인덱스와 값 자체를 추적을 위한 tracking 배열의 요소로 저장해 둔다.
2. LIS가 완성된 시점에, idx를 역으로 줄여가며 매칭되는 값들을 스택에 넣어 준다.
3. 2번 과정이 끝나면, 스택엔 증가 부분 수열이 역으로 저장되어 있다. 이를 하나씩 pop해 올바른 순서를 만들어 준다.

int idx = 0;
dp[0] = arr[0];
tracking[0] = new Pair(0, arr[0]);

for (int i = 1; i < N; i++) {
    if(dp[idx] < arr[i]) {
            dp[++idx] = arr[i];
            tracking[i] = new Pair(idx, arr[i]);
    } else {
            int targetIdx = binarySearch(idx, arr[i]);
            dp[targetIdx] = arr[i];
            tracking[i] = new Pair(targetIdx, arr[i]);
    }
}

위 이분 탐색에서 봤던 코드에 tracking 배열에도 값을 넣어주는 부분이 추가되었습니다.

수열 {10, 20, 10, 30, 20, 50}의 LIS 구하기

초기 tracking[0] 은 {0, 10}으로 설정해줍니다.

A[1]은 dp 배열 맨 뒤에 추가되었으므로, idx를 사용해 요소를 만들어 줍니다.

A[2]는 dp 배열에서 덮어씌우는 작업을 진행했으므로, targetIdx를 사용해 요소를 만들어 줍니다.

A[3]은 dp 배열 맨 뒤에 추가되었으므로, idx를 사용해 요소를 만들어 줍니다.

A[4]는 dp 배열에서 덮어씌우는 작업을 진행했으므로, targetIdx를 사용해 요소를 만들어 줍니다.

A[5]는 dp 배열 맨 뒤에 추가되었으므로, idx를 사용해 요소를 만들어 줍니다.

최종적으로 tracking 배열의 뒤부터 순회해, idx와 요소의 첫 번째 값 first 가 일치하면, 두 번째 값 second를 LIS로 채택합니다.

그 과정은 다음과 같습니다.

1. 위 경우에서 최초 idx값은 3이 됩니다. 맨 뒤 요소 tracking[5].first가 3이므로, tracking[5].second(50)를 스택에 넣고, idx는 감소되어 2가 됩니다.
2. tracking[3].first가 2이므로, tracking[3].second(30)를 스택에 넣고, idx는 1 감소시킨 1이 됩니다.
3. tracking[1].first가 1이므로, tracking[1].second(20)를 스택에 넣고, idx는 감소되어 0이 됩니다.
4. tracking[0].first가 0이므로, tracking[0].second(10)를 스택에 넣고 종료됩니다.