주어진 시퀀스에서 최장 증가 부분 수열(LIS)을 찾는 C++ 프로그램

최장 증가 부분 수열(LIS)이란?

최장 증가 부분 수열(Longest Increasing Subsequence, 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)을 활용하면 효율적으로 해결할 수 있습니다. 각 위치 i에 대해 'i번째 원소를 마지막으로 하는 최장 증가 부분 수열의 길이'를 length[i] 배열에 저장하고, 모든 값 중 최댓값을 구하면 됩니다. 시간 복잡도는 O(n²)입니다.

longestSubSeq(subarray, n)

입력: 부분 배열과 그 크기

출력: 최장 증가 부분 수열의 길이

시작
    크기가 n인 배열 length를 선언한다
    length의 모든 요소를 0으로 초기화한다
    i := 1 부터 n-1 까지 반복
        j := 0 부터 i-1 까지 반복
            만약 subarray[j] < subarray[i] 이고 length[j] > length[i] 라면
                length[i] := length[j]
        반복 종료
        length[i]를 1 증가시킨다
    반복 종료
    lis := 0
    i := 0 부터 n-1 까지 반복
        lis := lis 와 length[i] 중 최댓값
    반복 종료
    lis 반환
종료

예제 코드

#include <iostream>
using namespace std;
int longestSubSeq(int subArr[], int n) {
    int 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 << "최장 증가 부분 수열의 길이는: " << longestSubSeq(arr, n);
   return 0;
}

실행 결과

최장 증가 부분 수열의 길이는: 6