가장 긴 바이토닉 부분 수열(Longest Bitonic Subsequence) 구하기

바이토닉(bitonic) 수열은 처음에는 증가하다가 이후에는 감소하는 형태의 수열을 말합니다. 이 문제에서는 양의 정수로만 이루어진 배열이 주어지며, 그중에서 먼저 증가한 뒤 감소하는 부분 수열(subsequence)을 찾아 그 최대 길이를 구해야 합니다.

이 문제를 해결하기 위해 두 개의 보조 배열을 정의합니다. 하나는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence), 다른 하나는 최장 감소 부분 수열(LDS, Longest Decreasing Subsequence)입니다. LIS 배열은 array[i]로 끝나는 증가 부분 수열의 길이를 저장하고, LDS 배열은 array[i]에서 시작하는 감소 부분 수열의 길이를 저장합니다. 이 두 배열을 조합하면 가장 긴 바이토닉 부분 수열의 길이를 효율적으로 구할 수 있습니다.

입력과 출력

입력:
숫자 수열 {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

출력:
가장 긴 바이토닉 부분 수열의 길이 → 7

동작 원리

각 인덱스 i에 대해 LIS[i]는 i에서 끝나는 최장 증가 부분 수열의 길이를, LDS[i]는 i에서 시작하는 최장 감소 부분 수열의 길이를 나타냅니다. 인덱스 i가 바이토닉 수열의 꼭짓점(peak)이라면, 해당 요소가 증가 구간과 감소 구간 양쪽에 모두 포함되므로 전체 길이는 LIS[i] + LDS[i] − 1이 됩니다. 모든 인덱스에 대해 이 값을 계산한 뒤 그중 최댓값을 선택하면 됩니다.

이 알고리즘의 시간 복잡도는 O(n²)이며, 필요한 추가 공간은 O(n)입니다.

알고리즘

longBitonicSub(array, size)

입력: 배열과 배열의 크기(size)

출력: 가장 긴 바이토닉 부분 수열의 최대 길이

Begin
    incSubSeq를 배열과 같은 크기로 정의
    incSubSeq의 모든 값을 1로 초기화

    for i := 1 to size - 1, do
        for j := 0 to i - 1, do
            if array[i] > array[j] and incSubSeq[i] < incSubSeq[j] + 1, then
                incSubSeq[i] := incSubSeq[j] + 1
        done
    done

    decSubSeq를 배열과 같은 크기로 정의
    decSubSeq의 모든 값을 1로 초기화

    for i := size - 2 down to 0, do
        for j := size - 1 down to i + 1, do
            if array[i] > array[j] and decSubSeq[i] < decSubSeq[j] + 1, then
                decSubSeq[i] := decSubSeq[j] + 1
        done
    done

    max := incSubSeq[0] + decSubSeq[0] - 1
    for i := 1 to size - 1, do
        if incSubSeq[i] + decSubSeq[i] - 1 > max, then
            max := incSubSeq[i] + decSubSeq[i] - 1
    done

    return max
End

C++ 예제 코드

#include<iostream>
using namespace std;

int longBitonicSub(int arr[], int size) {
    int *increasingSubSeq = new int[size];      // 증가 부분 수열 배열 생성
    for (int i = 0; i < size; i++)
        increasingSubSeq[i] = 1;                // 모든 값을 1로 초기화

    // 왼쪽에서 오른쪽으로 진행하며 LIS 계산
    for (int i = 1; i < size; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
                increasingSubSeq[i] = increasingSubSeq[j] + 1;

    int *decreasingSubSeq = new int[size];      // 감소 부분 수열 배열 생성
    for (int i = 0; i < size; i++)
        decreasingSubSeq[i] = 1;                // 모든 값을 1로 초기화

    // 오른쪽에서 왼쪽으로 진행하며 LDS 계산
    for (int i = size - 2; i >= 0; i--)
        for (int j = size - 1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
                decreasingSubSeq[i] = decreasingSubSeq[j] + 1;

    int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
    for (int i = 1; i < size; i++)              // 최대 길이 탐색
        if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
            max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
    return max;
}

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 bitonic subsequence is " << longBitonicSub(arr, n);
}

실행 결과

Length of longest bitonic subsequence is 7