정수형 배열이 주어졌을 때, 함수를 활용하여 해당 배열의 비토닉성(Bitonicity)을 계산하는 것이 목표입니다.
배열의 비토닉성이란?
배열의 비토닉성은 다음 규칙에 따라 정의됩니다.
- 초기값은 0으로 설정합니다.
- 다음 요소가 이전 요소보다 크면 1씩 증가시킵니다.
- 다음 요소가 이전 요소보다 작으면 1씩 감소시킵니다.
예시
입력: arr[] = { 1,4,3,5,2,9,10,11}
출력: 배열의 비토닉성 : 3동작 설명
- 비토닉성을 계산할 변수 temp를 0으로 초기화합니다.
- 배열의 첫 번째 요소부터 시작해 arr[i]와 arr[i-1]을 차례로 비교합니다. 예를 들어 4와 1을 비교하면 4가 더 크므로 temp를 1 증가시키고, 이어서 4와 3을 비교하면 3이 더 작으므로 temp를 1 감소시킵니다.
- 모든 요소를 순회한 뒤 최종 temp 값인 3을 출력합니다.
접근 방법
- 크기가 n인 배열 arr[n]의 모든 요소를 처음부터 끝까지 순회합니다.
- arr[i] > arr[i-1]이면 bitonicity = bitonicity + 1
- arr[i] < arr[i-1]이면 bitonicity = bitonicity - 1
- arr[i] = arr[i-1]이면 bitonicity는 변하지 않습니다.
알고리즘
시작
1단계 → 배열의 비토닉성을 계산하는 함수 선언
int cal_bitonicity(int arr[], int n)
int temp = 0 으로 설정
반복문: int i = 1; i < n; i++
IF (arr[i] > arr[i - 1])
temp++ (증가)
End
ELSE IF (arr[i] < arr[i - 1])
temp-- (감소)
End
return temp
2단계 → main() 함수에서
int arr[] = { 1,4,3,5,2,9,10,11} 선언
int n = sizeof(arr) / sizeof(arr[0]) 설정
cal_bitonicity(arr, n) 호출
종료C++ 코드 구현
#include <iostream>
using namespace std;
// 배열의 비토닉성 계산
int cal_bitonicity(int arr[], int n) {
int temp = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1])
temp++;
else if (arr[i] < arr[i - 1])
temp--;
}
return temp;
}
int main() {
int arr[] = { 1,4,3,5,2,9,10,11};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열의 비토닉성 : "<<cal_bitonicity(arr, n);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
배열의 비토닉성 : 3시간 복잡도
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리 없이 상수 공간 O(1)만 사용하므로 매우 효율적입니다.