배열의 비토닉성(Bitonicity)은 배열 내 요소들의 증가·감소 추세를 하나의 수치로 표현한 값입니다. 인접한 두 요소를 비교할 때마다 값을 더하거나 빼는 간단한 규칙으로 계산할 수 있습니다.
비토닉성의 정의
비토닉성은 다음과 같은 규칙에 따라 정의됩니다.
Bitonicity = 0 (초기값) i는 1부터 n-1까지 반복 arr[i] > arr[i-1] 이면 : Bitonicity = Bitonicity + 1 arr[i] < arr[i-1] 이면 : Bitonicity = Bitonicity - 1 arr[i] = arr[i-1] 이면 : Bitonicity 변화 없음
즉, 이전 요소보다 값이 커질 때마다 1씩 증가하고, 작아질 때마다 1씩 감소합니다. 값이 같으면 변하지 않습니다.
알고리즘 설명
배열의 비토닉성을 구하기 위해 bitonicity라는 변수를 사용합니다. 이 변수는 배열의 현재 요소와 이전 요소를 비교한 결과에 따라 값이 갱신됩니다. 위에서 설명한 로직을 배열의 첫 번째 요소부터 마지막 요소까지 차례대로 적용하면, 순회가 끝난 시점의 변수 값이 곧 해당 배열의 최종 비토닉성이 됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int main() {
int arr[] = { 1, 2, 4, 5, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int Bitonicity = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1])
Bitonicity++;
else if (arr[i] < arr[i - 1])
Bitonicity--;
}
cout << "Bitonicity = " << Bitonicity;
return 0;
}출력 결과
Bitonicity = 1
결과 분석
예제 배열 { 1, 2, 4, 5, 4, 3 }의 경우를 살펴보겠습니다.
- 증가 구간: 1→2, 2→4, 4→5 (총 3번 증가)
- 감소 구간: 5→4, 4→3 (총 2번 감소)
따라서 최종 비토닉성은 3 − 2 = 1이 됩니다. 이 값은 배열이 전체적으로 증가 추세인지, 감소 추세인지, 또는 어느 쪽으로 기울어져 있는지를 한눈에 파악하는 데 유용하게 활용될 수 있습니다.