C++로 가장 긴 바이토닉 부분 수열의 길이 구하기

숫자 배열이 주어졌을 때, 그중에서 가장 긴 바이토닉(bitonic) 부분 수열의 길이를 찾는 문제입니다. 바이토닉 수열이란 처음에는 엄격하게(strictly) 증가하다가 이후에는 엄격하게 감소하는 수열을 의미합니다. 단, 순수하게 증가만 하거나 감소만 하는 수열 역시 바이토닉 수열로 간주됩니다.

예를 들어 입력이 nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]이고 수열의 크기가 16이라면, 결과는 7이 됩니다.

문제 해결 접근 방법

이 문제는 동적 프로그래밍(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 각 위치 i를 기준으로, 왼쪽에서 시작해 i로 끝나는 최장 증가 부분 수열(LIS)의 길이를 계산합니다.

• 같은 위치 i에서 시작해 오른쪽으로 이어지는 최장 감소 부분 수열(LDS)의 길이를 계산합니다.

• 두 길이의 합에서 1을 빼면(꼭짓점 요소가 중복 계산되므로) 해당 위치를 꼭짓점으로 하는 바이토닉 수열의 길이가 됩니다. 이 값들 중 최대값이 곧 정답입니다.

알고리즘 단계

1. 입력 배열과 같은 크기의 increasingSubSeq 배열을 생성하고 모든 값을 1로 초기화합니다.

2. i = 1부터 size - 1까지 반복하며, 내부 루프에서 j = 0부터 i - 1까지 탐색합니다. 이때 arr[i] > arr[j]이고 increasingSubSeq[i] < increasingSubSeq[j] + 1이면 increasingSubSeq[i] = increasingSubSeq[j] + 1로 갱신합니다.

3. 같은 크기의 decreasingSubSeq 배열을 생성하고 1로 초기화한 뒤, i = size - 2부터 0까지 거꾸로 순회하며 동일한 방식으로 최장 감소 부분 수열의 길이를 계산합니다.

4. max = increasingSubSeq[0] + decreasingSubSeq[0] - 1로 초기화한 후, 나머지 인덱스에서 increasingSubSeq[i] + decreasingSubSeq[i] - 1 값이 더 크면 max를 갱신합니다.

5. 최종적으로 max를 반환합니다.

다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#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;
    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;
    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 << longBitonicSub(arr, n);
}

입력

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

출력

7

동작 원리 설명

위 코드에서 increasingSubSeq 배열은 왼쪽에서 오른쪽으로 각 요소에서 끝나는 최장 증가 부분 수열의 길이를 저장하고, decreasingSubSeq 배열은 오른쪽에서 왼쪽으로 각 요소에서 시작하는 최장 감소 부분 수열의 길이를 저장합니다. 예제 입력의 경우 [0, 4, 10, 14, 9, 5, 3]처럼 증가 후 감소하는 길이 7짜리 바이토닉 부분 수열이 존재하므로 결과는 7이 됩니다.

이 알고리즘의 시간 복잡도는 O(n²), 공간 복잡도는 O(n)입니다.