개념
주어진 두 개의 배열을 이용해 가장 긴 바이토닉(bitonic) 수열을 찾는 것이 이 문제의 목표입니다. 바이토닉 수열이란 처음에는 계속 증가하다가 이후에는 계속 감소하는 형태의 수열을 의미합니다. 여기서 중요한 제약 조건은, 증가하는 부분은 반드시 첫 번째 배열(arr1)의 부분 수열이어야 하고, 감소하는 부분은 반드시 두 번째 배열(arr2)의 부분 수열이어야 한다는 점입니다.
입력 예제 1
arr1[] = {2, 6, 3, 5, 4, 6},
arr2[] = {9, 7, 5, 8, 4, 3}
출력
2, 3, 4, 6, 9, 7, 5, 4, 3
위 결과에서 2 → 3 → 4 → 6은 첫 번째 배열에서 추출한 증가 부분이며, 9 → 7 → 5 → 4 → 3은 두 번째 배열에서 추출한 감소 부분입니다.
입력 예제 2
arr1[] = {3, 1, 2, 4, 5},
arr2[] = {6, 4, 3, 2}
출력
1, 2, 4, 5, 6, 4, 3, 2
접근 방법
핵심 아이디어는 매우 단순합니다. 첫 번째 배열에서 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)을 구하고, 두 번째 배열에서 최장 감소 부분 수열을 구한 뒤, 이 둘을 연결하면 원하는 바이토닉 수열이 완성됩니다.
- 1단계: 첫 번째 배열(arr1)에 대해 이분 탐색 기반 LIS 알고리즘을 적용해 최장 증가 수열을 구합니다.
- 2단계: 두 번째 배열(arr2)을 뒤집은 뒤 동일한 LIS 알고리즘을 적용하면, 원래 배열 기준의 최장 감소 수열을 얻을 수 있습니다.
- 3단계: 두 결과를 이어 붙여 최종 바이토닉 수열을 출력합니다.
C++ 구현 예제
// 증가 부분은 첫 번째 배열에서, 감소 부분은 두 번째 배열에서
// 가져오는 가장 긴 바이토닉 수열을 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
vector<int> res1;
// 이분 탐색 유틸리티 함수
int GetCeilIndex(int arr[], vector<int>& T1, int l1,
int r1, int key1){
while (r1 - l1 > 1) {
int m1 = l1 + (r1 - l1) / 2;
if (arr[T1[m1]] >= key1)
r1 = m1;
else
l1 = m1;
}
return r1;
}
// LIS를 역방향 형태로 구하는 함수
void LIS(int arr[], int n){
// 배열 크기가 0일 때의 경계 조건 처리용
vector<int> tailIndices1(n, 0); // 0으로 초기화
vector<int> prevIndices1(n, -1); // -1로 초기화
int len1 = 1; // 항상 빈 위치를 가리킴
for (int i = 1; i < n; i++) {
// 새로운 최솟값인 경우
if (arr[i] < arr[tailIndices1[0]])
tailIndices1[0] = i;
// arr[i]가 현재 가장 긴 부분 수열을 확장하는 경우
else if (arr[i] > arr[tailIndices1[len1 - 1]]) {
prevIndices1[i] = tailIndices1[len1 - 1];
tailIndices1[len1++] = i;
}
// arr[i]가 이후 부분 수열의 후보가 되는 경우
// tailIndices에서 ceil 위치의 값을 대체
else {
int pos1 = GetCeilIndex(arr, tailIndices1, -1,
len1 - 1, arr[i]);
prevIndices1[i] = tailIndices1[pos1 - 1];
tailIndices1[pos1] = i;
}
}
// 구한 LIS(최장 증가 수열)를 벡터에 저장
for (int i = tailIndices1[len1 - 1]; i >= 0; i =
prevIndices1[i])
res1.push_back(arr[i]);
}
// 가장 긴 바이토닉 수열을 찾는 함수
void longestBitonic(int arr1[], int n1, int arr2[], int n2){
// 첫 번째 배열의 LIS를 역방향 형태로 구함
LIS(arr1, n1);
// res를 뒤집어 첫 번째 배열의 LIS를 얻음
reverse(res1.begin(), res1.end());
// 두 번째 배열을 뒤집은 뒤 LIS를 구함
reverse(arr2, arr2 + n2);
LIS(arr2, n2);
// 결과 출력
for (int i = 0; i < res1.size(); i++)
cout << res1[i] << " ";
}
// 드라이버 코드
int main(){
cout<<"Example:"<< endl;
int arr1[] = {3, 1, 2, 4, 5};
int arr2[] = {6, 4, 3, 2};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
longestBitonic(arr1, n1, arr2, n2);
return 0;
}
실행 결과
Example: 1 2 4 5 6 4 3 2
동작 원리 정리
이 알고리즘은 O(n log n)의 시간 복잡도로 동작합니다. 일반적인 DP 기반 LIS(O(n²))와 달리, tailIndices 배열과 이분 탐색(GetCeilIndex)을 활용하기 때문에 각 원소를 처리하는 데 로그 시간만 걸립니다. 또한 prevIndices 배열에 이전 원소의 인덱스를 저장해 두면, 마지막에 역추적을 통해 실제 수열을 복원할 수 있습니다.
특히 두 번째 배열을 뒤집어서 LIS를 구하는 트릭 덕분에 별도의 최장 감소 수열(LDS) 알고리즘을 작성할 필요 없이 동일한 LIS 함수를 그대로 재사용할 수 있다는 점이 이 구현의 큰 장점입니다.