배열에 등비수열(기하수열)의 원소들이 순서대로 저장되어 있고, 그중 한 개의 원소가 누락되어 있다고 가정해 보겠습니다. 우리의 목표는 바로 이 누락된 원소를 찾아내는 것입니다. 예를 들어 배열이 arr = [1, 3, 27, 81]이라면 공비가 3인 등비수열에서 9가 빠져 있으므로, 출력 결과는 9가 되어야 합니다.
접근 방식: 이진 탐색 활용
이 문제는 이진 탐색(binary search)을 활용하면 O(log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 처음부터 끝까지 모든 원소를 하나씩 확인하는 선형 탐색(O(n))보다 훨씬 빠른 방법입니다.
알고리즘의 핵심 아이디어는 다음과 같습니다.
- 배열의 중간 원소(mid)를 선택합니다.
- mid 위치의 원소와 mid + 1 위치의 원소 사이의 비율이 공비(common ratio)와 일치하는지 확인합니다.
- 일치하지 않는다면, 누락된 원소는 mid와 mid + 1 인덱스 사이에 존재하며 그 값은 arr[mid] * ratio입니다.
- 만약 arr[mid]가 수열의 첫 번째 원소에 공비를 mid번 거듭제곱한 값(arr[0] * ratio^mid)과 같다면, 왼쪽 부분은 정상이므로 누락된 원소는 오른쪽 절반에 있습니다.
- 그렇지 않다면 누락된 원소는 왼쪽 절반에 있으므로 탐색 범위를 왼쪽으로 좁혀 다시 탐색합니다.
C++ 구현 예제
#include <iostream>
#include <cmath>
using namespace std;
class Progression {
public:
int missingUtil(int arr[], int left, int right, int ratio) {
if (right <= left)
return INT_MAX;
int mid = left + (right - left) / 2;
if (arr[mid + 1] - arr[mid] != ratio)
return (arr[mid] * ratio);
if (mid > 0 && arr[mid] / arr[mid - 1] != ratio)
return (arr[mid - 1] * ratio);
if (arr[mid] == arr[0] * pow(ratio, mid))
return missingUtil(arr, mid + 1, right, ratio);
return missingUtil(arr, left, mid - 1, ratio);
}
int missingElement(int arr[], int n) {
int ratio = pow(arr[n-1]/arr[0], 1.0/n);
return missingUtil(arr, 0, n - 1, ratio);
}
};
int main() {
Progression pg;
int arr[] = {1, 3, 27, 81};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The missing element is: " << pg.missingElement(arr, n);
}
실행 결과
The missing element is: 9
위 코드에서 공비는 pow(arr[n-1]/arr[0], 1.0/n)을 통해 계산됩니다. 이는 길이가 n인 등비수열에서 마지막 항과 첫 번째 항의 비율이 공비의 n제곱과 같다는 성질을 이용한 것입니다. 이후 재귀 함수 missingUtil이 탐색 범위를 절반씩 줄여가며 누락된 원소를 찾아냅니다.