가장 긴 증가 부분 수열(LIS) – 동적 계획법으로 구현하기

가장 긴 증가 부분 수열(Longest Increasing Subsequence, LIS)은 수열 내에서 각 원소가 자신의 앞 원소보다 큰 값을 갖도록 유지되는 부분 수열입니다. 이 글에서는 주어진 정수 집합에서 가장 긴 증가 부분 수열의 길이를 찾는 방법을 알아보겠습니다.

문제 이해하기

LIS 문제는 원본 배열의 순서를 그대로 유지한 채 일부 원소를 골라내어, 선택된 원소들이 오름차순이 되도록 만들 때 선택할 수 있는 최대 개수를 구하는 것입니다. 반드시 연속된 구간일 필요는 없으며, 떨어져 있는 원소들을 조합할 수 있다는 점이 특징입니다.

입력 및 출력 예시

입력:
정수 집합 {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

출력:
가장 긴 증가 부분 수열의 길이: 6
해당 부분 수열: 0, 2, 6, 9, 13, 15

알고리즘 설계

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

length[i]: subArr[i]를 마지막 원소로 하는 증가 부분 수열의 최대 길이를 저장합니다.
i번째 원소보다 작은 앞선 원소 j(subArr[j] < subArr[i])를 찾아, length[j]가 현재 length[i]보다 크면 값을 갱신합니다.
모든 원소를 처리한 뒤 length 배열의 최댓값이 곧 LIS의 길이가 됩니다.

의사 코드(Pseudocode)

longestSubSeq(subarray, n)

입력 − 부분 배열과 배열의 크기 n
출력 − 가장 긴 증가 부분 수열의 길이

Begin
    크기가 n인 배열 length를 선언
    length의 모든 요소를 0으로 초기화

    for i := 1 to n-1, do
        for j := 0 to i-1, do
            if subarray[j] < subarray[i] and length[j] > length[i], then
                length[i] := length[j]
        done
        length[i]를 1 증가
    done

    lis := 0
    for i := 0 to n-1, do
        lis := lis와 length[i] 중 최댓값
    done

    return lis
End

C++ 구현 예제

#include <iostream>
using namespace std;

int longestSubSeq(int subArr[], int n) {
    int length[n];
    fill(length, length + n, 0);       // 모든 length 값을 0으로 초기화
    length[0] = 1;                     // subArr[0]으로 끝나는 부분 수열의 길이는 1

    for (int i = 1; i < n; i++) {      // 두 번째 원소부터 마지막까지 탐색
        for (int j = 0; j < i; j++) {  // subArr[j]로 끝나는 부분 수열 확인
            if (subArr[j] < subArr[i] && length[j] > length[i])
                length[i] = length[j];
        }
        length[i]++;                   // arr[i]를 부분 수열에 추가
    }

    int lis = 0;
    for (int i = 0; i < n; i++)        // 가장 긴 증가 부분 수열의 길이 찾기
        lis = max(lis, length[i]);
    return lis;
}

int main() {
    int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
    int n = 16;
    cout << "Length of Longest Increasing Subsequence is: " << longestSubSeq(arr, n);
    return 0;
}

실행 결과

Length of Longest Increasing Subsequence is: 6

복잡도 분석

위 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 공간 복잡도는 길이 정보를 저장하는 배열 하나만 사용하므로 O(n)입니다. 참고로 이진 탐색을 함께 활용하면 O(n log n)의 시간 복잡도로 더 빠르게 해결할 수도 있습니다.