이 C++ 프로그램은 분할 정복(Divide and Conquer) 기법과 피보나치 수(Fibonacci Number)를 활용한 피보나치 탐색(Fibonacci Search)을 구현합니다. 피보나치 수열의 값을 이용해 정렬된 데이터 배열의 탐색 위치(mid)를 계산하고, 그 위치를 기준으로 원하는 데이터 항목을 찾아냅니다. 이 방식의 시간 복잡도는 O(log(n))로, 이진 탐색과 동일한 수준의 효율성을 보입니다.
피보나치 탐색의 동작 원리
피보나치 탐색은 정렬된 배열에서 특정 요소를 찾는 알고리즘이라는 점에서 이진 탐색(Binary Search)과 유사합니다. 하지만 탐색 범위를 단순히 절반으로 나누는 대신, 피보나치 수열의 값을 이용해 다음 탐색 위치를 결정한다는 차이가 있습니다. 이 과정에서 곱셈이나 나눗셈 연산 없이 덧셈과 뺄셈만으로 탐색 범위를 좁혀 나갈 수 있으며, 재귀 호출을 통해 남은 하위 배열에서 동일한 절차를 반복합니다.
알고리즘
시작
배열에 데이터를 정렬된 상태로 저장한다.
검색할 요소를 입력받는다.
FibonacciSearch() 함수를 호출한다.
'start + fib[index-2]' 표현식으로 mid 값을 계산한다.
찾으려는 값이 mid 인덱스의 값과 같으면 결과를 출력하고 main으로 복귀한다.
찾으려는 값이 mid 인덱스의 값보다 작으면 왼쪽 하위 배열에서 탐색을 계속한다.
찾으려는 값이 mid 인덱스의 값보다 크면 오른쪽 하위 배열에서 탐색을 계속한다.
계산된 mid 값이 start 또는 end와 같다면 해당 요소는 배열에 존재하지 않는 것이다.
끝
예제 코드
#include<iostream>
using namespace std;
void FibonacciSearch(int *a, int start, int end, int *fib, int index, int item) {
int i, mid;
mid = start+fib[index-2];
if(item == a[mid]) {
cout<<" item found at "<<mid<<" index.";
return;
} else if(item == a[start]) {
cout<<" item found at "<<start<<" index.";
return;
} else if(item == a[end]) {
cout<<" item found at "<<end<<" index.";
return;
} else if(mid == start || mid == end) {
cout<<" Element not found";
return;
} else if(item > a[mid])
FibonacciSearch(a, mid, end, fib, index-1, item);
else
FibonacciSearch(a, start, mid, fib, index-2, item);
}
main() {
int n, i, fib[20], a[10]={3, 7, 55, 86, 7, 15, 26, 30, 46, 95};
char ch;
fib[0] = 0;
fib[1] = 1;
i = 1;
while(fib[i] < 10) {
i++;
fib[i] = fib[i-1] + fib[i-2];
}
up:
cout<<" Enter the Element to be searched: ";
cin>>n;
FibonacciSearch(a, 0, 9, fib, i, n);
cout<<" Do you want to search more...enter choice(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;
return 0;
}
코드 설명
먼저 main() 함수에서 피보나치 수열을 생성합니다. fib[0]=0, fib[1]=1로 초기화한 뒤, 배열의 크기(10)보다 작은 피보나치 수들이 담길 때까지 반복문으로 수열을 확장합니다. 사용자가 검색할 값을 입력하면 FibonacciSearch() 함수가 호출되며, 이 함수는 다음과 같이 동작합니다.
- mid 계산: 현재 시작점(start)에 피보나치 값을 더해 탐색 위치를 정합니다.
- 일치 여부 확인: mid, start, end 위치의 값과 비교하여 일치하면 해당 인덱스를 출력합니다.
- 범위 축소: 찾는 값이 더 크면 오른쪽 부분 배열로(index를 1 감소), 더 작으면 왼쪽 부분 배열로(index를 2 감소) 재귀 호출합니다.
- 종료 조건: mid가 start 또는 end와 같아지면 더 이상 탐색할 범위가 없으므로 'Element not found'를 출력합니다.
실행 결과
Enter the Element to be searched: 26
item found at 6 index.
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 45
item not found
Do you want to search more...enter choice(y/n)?n
실행 결과를 보면 값 26은 인덱스 6에서 성공적으로 발견되었고, 배열에 존재하지 않는 값 45는 찾지 못했다는 메시지와 함께 탐색이 종료되었습니다. 사용자가 y 또는 Y를 입력하는 한 반복해서 값을 검색할 수 있도록 goto 문으로 루프가 구성되어 있습니다.