어떤 데이터 집합이 있을 때 ‘검색만 하면 되는 경우’, 검색에 사용할 알고리즘은 단순히 ‘탐색 계산 시간이 짧은 알고리즘’을 선택하면 됩니다. 그러나 데이터 집합에 대한 검색뿐 아니라 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외에 작업에 소요되는 비용을 종합적으로 하여 알고리즘을 선택해야 합니다. 예를 들어, 데이터 추가를 자주하는 경우 검색(탐색) 속도가 빠르더라도 데이터의 추가비용이 많이 들어가는 알고리즘은 피해야합니다.
<aside> 💡
어떤 경우에 데이터 추가 비용이 더 많이 들까요?
예를 들어, 학생의 번호 순서대로 키의 값을 넣은 배열이 있다고 가정할 경우 학생의 번호만 알면 바로 키 값을 알 수 있습니다. 하지만 새로운 학생이 전학을 와서 중간에 데이터를 추가해야할 경우, 데이터를 추가한 중간 지점 이후의 학생 순서를 모두 뒤로 밀어 넣는 작업을 해야합니다. 바로 이런 경우 ‘배열은 검색은 빠르지만 데이터를 추가하기 위한 비용이 많이 든다’ 라고 합니다.
</aside>
/* 선형 검색(보초법, sentinel method) */
#include <stdio.h>
#include <stdlib.h>
/* 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법) */
int search(int a[], int n, int key)
{
int i = 0;
a[n] = key; /* 보초(sentinel) 추가 */
while(1) {
if(a[i] == key)
break; /* 원하는 key 값을 찾은 경우 */
i++;
}
return i == n ? -1 : i;
}
int main(void)
{
int i, nx, ky, idx; /* 배열의 첫 번째 요소에 대한 포인터 */
int *x;
puts("선형 검색(보초법)");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx + 1, sizeof(int)); /* 요소의 개수가 (nx+1)인 int형 배열을 생성 */
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
printf("검색값 : ");
scanf("%d", &ky);
idx = search(x, nx, ky); /* 배열 x에서 값이 ky인 요소를 선형 검색 */
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\\n", ky, idx);
free(x);
return 0;
}
이진 검색 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다는 것입니다. 이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있습니다.
이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다.
/* 이진 탐색 */
#include <stdio.h>
#include <stdlib.h>
/* 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 이진 검색 */
int bin_search(const int a[], int n, int key)
{
int pl = 0; // 검색 범위 맨 앞의 인덱스
int pr = n - 1; // 검색 범위 맨 끝의 인덱스
int pc; // 검색 범위 맨 한가운데의 인덱스
do {
pc = (pl + pr) / 2;
if(a[pc] == key) // 검색 성공
return pc;
else if(a[pc] < key)
pl = pc + 1;
else
pr = pc - 1;
} while(pl <= pr);
return -1;
}
int main(void)
{
int i, nx, ky, idx; // 배열의 첫 번째 요소에 대한 포인터
int *x;
puts("이진 검색");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int)); // 요소의 개수가 nx인 int형 배열을 생성
printf("오름차순으로 입력하세요.\\n");
printf("x[0] : ");
scanf("%d", &x[0]);
for(i = 1; i < nx; i++) {
do {
printf("x[%d]: ", i);
scanf("%d", &x[i]);
} while(x[i] < x[i - 1]); // 바로 앞의 값보다 작으면 다시 입력
}
printf("검색값 : ");
scanf("%d", &ky);
idx = bin_search(x, nx, ky); // 배열 x에서 값이 ky인 요소를 이진 검색
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d는(은) x[%d]에 있습니다.\\n", ky, idx);
free(x); // 배열 동적 할당된 메모리 해제
return 0;
}
'보초법'은 알고리즘의 한 종류로, 특히 선형 검색(Linear Search)의 효율성을 높이기 위한 방법입니다.
선형 검색은 배열의 처음부터 끝까지 순서대로 탐색하며 원하는 값을 찾는 가장 기본적인 검색 방법입니다. 이 때, 검색을 종료하는 조건은 크게 두 가지입니다.