관리 메뉴
촉촉한초코칩
03. 검색 본문
03-1 검색 알고리즘
검색 기법 3가지
- 배열 검색
- 선형 리스트 검색 : 무작위로 늘어놓은 데이터 모임에서 검색 수행
- 이진검색트리 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색 수행
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 빠른 검색 수해
- 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
* 추가/삭제가 자주 일어나는 경우 비용이 많이 든다.
03-2 선형 검색 (linear search)
선형 검색 (순차 검색 sequential search)
- 원하는 키 값을 갖는 요소를 만날 때까지 앞에서부터 순서대로 요소를 검색하는 것
배열 검색의 종료 조건
- 검색할 값을 발견하지 못하고 배열 끝을 지나간 경우 > 검색 실패
- 검색할 값과 같은 요소를 발견한 경우 > 검색 성공
#include <stido.h>
#include <stdlib.h>
int search(const int a[], int n, int key) {
int i=0;
while(1) {
if(i==n)
return -1; //검색 실패
if(a[i] == key)
return i; //검색 성공
i++;
}
for(i=0; i<n; i++)
if(a[i] == key)
return i; //검색 성공
return -1; //검색 실패
}
int main(void) {
int i, nx, ky, idx;
int *x;
puts("선형검색 ");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i=0; i<nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
printf("검색값 : ");
scanf("%d", &ky);
idx = search(x, nx, ky);
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}search 함수
- 배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색한다.
- 반환값 > 발견한 요소의 인덱스
- 값이 key인 요소가 여러 개 존재하면 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 된다.
- 값이 key인 요소가 존재하지 않으면 -1을 반환한다.
* 무한 루프 구현
| while(1) { } | for(; ; ) { } | do { } while(1); |
보초법 (sentinel method)
- 선형검색은 반복할 때마다 다음 종료 조건(검색 실패/성공)을 모두 체크함 > 종료 조건을 검사하는 비용이 꽤 많이 듦
- 보초법은 검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장 = 보초 (sentinel)
- 선형검색 : 검색 성공에 대한 코드 필요 + 검색에 실패했을 때 반복 횟수 > 2 * n번
- 보초법 : 검색 성공에 대한 코드 불필요 + 검색에 실패했을 때 반복 횟수 > n번
#include <stido.h>
#include <stdlib.h>
int search(const int a[], int n, int key) {
int i=0;
a[n]= key;
while(1) {
if(a[i] == key)
break;
i++;
}
return i==n? -1 : i; //i와 n이 같다 = 보초에 넣은 값과 같다 = 검색 실패
}
int main(void) {
int i, nx, ky, idx;
int *x;
puts("선형검색 ");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i=0; i<nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
printf("검색값 : ");
scanf("%d", &ky);
idx = search(x, nx, ky);
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}
03-3 이진 검색
이진 검색 (Binary Search)
- 데이터가 키 값으로 이미 정렬되어 있다. (오름차순/내림차순)
- 선형 검색보다 조금 더 빠르게 검색할 수 있다.
검색 과정
- 배열 중앙에 위치한 요소부터 검색 시작
- 배열 중앙 값 > 검색값 비교 : 검색 대상을 앞쪽으로 좁힌다.
- 배열 중앙 값 < 검색 값 비교 : 검색 대상을 뒤쪽으로 좁힌다.
- 다시 배열 중앙에 위치한 요소를 찾아 비교한다.
> 검색을 한 단계씩 진행할 때마다 검색 범위가 반으로 좁혀진다.
* 사용자가 각 요소의 값을 입력할 때는 바로 앞에 입력한 요소보다 크거나/작아야 한다.
n개의 요소가 오름차순으로 늘어선 배열 a에서 키를 이진 검색으로 검색하는 과정
- 검색 범위의 맨 앞 인덱스 : pl (0)
- 맨 끝 인덱스 : pr (n-1)
- 중앙 인덱스 : pc (n-1)/2
| a[pc] < key | 검색 범위 : a[pc+1] ~ a[pr] pl = pc + 1 pc = (pl + pr / 2) |
| a[pc] > key | 검색 범위 : a[pl] ~ a[pc-1] pr = pc-1 pc = (pl + pr) / 2 |
이진검색 비교횟수 평균값 : log n
알고리즘 종료 조건
- a[pc]와 key가 일치하는 경우 > log n - 1회
- 검색 범위가 더 이상 없는 경우 > [log(n+1)]회
* [x] : 천장 함수(ceiling funcion), 올림 함수 > x보다 크거나 같으면서 가장 작은 정수
#include <stdio.h>
#include <stdlib.h>
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));
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);
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(는)은 x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}
복잡도 (Complexity)
- 복잡도 : 알고리즘의 성능을 객관적으로 평가하는 기준
- 프로그램 실행 속도 > 하드웨어, 컴파일러 등 조건에 따라 달라진다.
복잡도 두 가지 요소
- 시간 복잡도 (time complexity) : 실행에 필요한 시간을 평가한 것
- 공간 복잡도 (space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
| 실행 횟수 | 복잡도 |
| 1 | O(1) |
| n | O(n) |
| log n | O(log n) |
* 2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시한다.
bsearch 함수(정렬된 배열에서 검색하는 함수)
- C언어의 표준 라이브러리, 다양한 요소의 자료형을 가진 배열에서도 검색 가능한 bsearch 함수 제공 > 일반 유틸리티(Utility) 함수
bsearch 함수의 특징과 요소
- 검색 대상의 배열은 항상 정렬되어 있어야 한다.
- 검색하는 값과 같은 요소가 여러 개 존재하는 경우, 항상 가장 앞쪽에 있는 요소를 찾아내는 것은 아니다.
| 헤더 | #include <stdlib.h> |
| 형식 | void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); |
| 해설 | 맨 처음 요소를 base가 가리키는 요소의 개수가 nmemb개이고 요소 크기가 size인 객체의 배열에서 key가 가리키는 객체와 일치하는 요소를 검색한다. compar이 가리키는 비교 함수는 key 객체에 대한 포인터를 첫 번째 인수로, 배열 요소에 대한 포인터를 두 번째 인수로 하여 호출한다. compar이 가리키는 비교 함수는 key 객체가 배열 요소보다 작으면 작은 값을, 일치하면 0을, 크면 큰 값을 반환하도록 작성해야 한다. compar이 가리키는 배열은 key 객체와 비교가 가능한 작은 요소, 같은 요소, 큰 요소의 세 부분으로 구성되어 있다. 이 세 부분이 소개한 순서로 존재해야 한다. |
| 반환값 | 검사하는 대상(배열) 중에 일치하는 요소에 대한 포인터를 반환한다. 일치하는 요소가 없다면 NULL 포인터를 반환한다. 두 요소의 값이 같을 때 어느 요소와 일치하는지는 규정되어 있지 않다. (사용자가 설정) |
bsearch 인수
| key | 키 값 (검색할 값이 저장된 객체에 대한 포인터) |
| base | 배열의 포인터 |
| nmemb | 배열이 요소 개수 |
| size | 배열의 요소 크기 |
| compar | 비교함수 > 이진 검색의 검색 과정에는 검색하는 키 값과 배열의 요소값을 비교하여 대소 관계를 판단하는 과정이 포함된다. > 두 값을 비교하고 어떤 값을 반환할지는 사용자가 직접 작성한다. |
#include <stdio.h>
#include <stdlib.h>
//정수 비교하는 함수 (오름차순)
int int_cmp(const int *a, const int *b) {
if(*a < *b) {
return -1;
else if(*a > *b) {
return 1;
else {
return 0;
// return *a < *b ? -1 : *a > *b ? 1 : 0;
}
int main(void) {
int i, nx, ky;
int *x; //배열의 첫 번째 요소에 대한 포인터
int *p; //검색한 요소에 대한 포인터
puts("bsearch 함수를 사용해서 검색 ");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(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);
p = bsearch(&ky, //검색값에 대한 포인터
x, //배열
nx, //요소 개수
sizeof(int), //요소 크기
(int(*)(const void *, const void *))int_cmp); //비교 함수
if(p == NULL)
puts("검색에 실패했습니다.");
else
printf("%d은(는) x[%d]에 있습니다.\n", ky, (int)(p-x));
free(x);
return 0;
}bsearch 함수 호출
- 비교함수가 받는 인수의 자료형 : int *
- bsearch 함수가 받는 비교 함수의 인수의 자료형 : void *
- > bsearch 함수 호출에 맞도록 형변환을 해야 한다.
- 이때 비교함수의 인수 자료형을 void로 바꾸면 형변환을 하지 않아도 된다. (필요에 따라 구현)
//캐스팅 없이 사용할 수 있는 비교 함수
int int_cmp (const void *a, const void *b) {
if(*(int*)a < *(int*)b)
return -1;
else if(*(int*)a > *(int*)b)
return 1;
else
return 0;
}bsearch 함수의 반환값
- 함수 반환값 : 검색을 통해 찾은 요소의 포인터
- 요소의 인덱스 : (요소 포인터 - 첫 번째 요소의 포인터)
- 만약 검색에 실패한 경우 : 널(NULL) 포인터 반환
* 내림차순으로 정렬된 배열에서 검색하기
#include <stdio.h>
#include <stdlib.h>
int int_cmpr(const int *a, const int *b) {
if(*a < *b)
return 1;
else if(*a > *b)
return -1;
else
return 0;
}
int main(void) {
int i, ky, nx;
int *x; //배열 첫번째 요소에 대한 포인터
int *p; //검색한 요소에 대한 포인터
puts("bsearch 함수를 사용하여 검색");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(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);
p = bsearch(&ky, //검색값에 대한 포인터
x, //배열
nx, //요소 개수
sizeof(int), //요소 크기
(int(*)(const void *, const void *)) int_cmpr); //비교 함수
if(p == NULL)
puts("검색에 실패했습니다");
else
printf("%d는(은) x[%d]에 있습니다.\n", ky, (int)(p-x));
free(x);
return 0;
}
* 함수 포인터
- 함수를 가리키는 포인터
- 함수 포인터의 자료형 : 가리키는 함수에 따라 다르다.
- *변수명 : 객체에 대한 포인터 선언
- (*변수명) : 포인터를 반환하는 함수
- 함수 이름 = 그 함수에 대한 포인터
double func(int); //int를 받아들여 double을 반환하는 함수
double(*fp)(int); //int를 받아들여 double을 반환하는 함수에 대한 포인터 fp 선언
double *fn(int); //int를 받아들여 double에 대한 포인터를 반환하는 함수 선언#include <stdio.h>
int sum(int x1, int x2) {
return x1 + x2;
}
int mul(int x1, int x2) {
return x1 * x2;
}
//sum, mul 함수에 대한 포인터를 매개변수 calc로 받아들인다.
//받아들인 함수에 대한 포인터를 사용하는 코드 : (*calc)(i,j)
//함수에 대한 포인터에 간접연산자 *를 사용하면 그 포인터가 가리키는 함수가 호출된다.
//해당 코드는 컴파일할 때가 아니라 실행할 때 실제로 어떤 함수를 호출할지 결정한다.
void kuku(int(*calc)(int, int)) {
int i, j;
for(i=1; i<=9; i++) {
for(j=1; j<=9; j++)
printf("%3d", (*calc)(i,j));
putchar('\n');
}
}
//함수에 대한 포인터는 매개변수 선언에서만 변수 이름 앞에 *와 ()를 생략한 형식으로 선언할 수 있다.
//void kuku(int calc(int int)) {
// int i, j;
// ...
//}
int main(void) {
puts("덧셈표");
kuku(sum);
puts("\n 곱셈표 ");
kuku(mul);
return 0;
}
- 함수에 대한 포인터를 사용하면 호출하는 함수를 실행하여 결정하는 동적 함수 호출을 구현할 수 있다.
- 동적 함수 호출을 사용하면 사용자가 원하는 경우에 sum/mul 함수를 직접 작성하여 호출하지 않아도 실행할 수 있다.
- 함수에 대한 포인터는 매개변수 선언에서만 변수 이름 앞에 *와 ()를 생략한 형식으로 선언할 수 있다.
- 배열을 매개변수로 하는 함수에서 int *p를 int p[]로 선언하는 것과 비슷하다.
- 함수 호출식의 왼쪽 피연산자는 함수 포인터가 아닌 함수 이름을 사용해도 된다 > calc(i, j)
구조체 배열에서 검색하기
#include <stdio.h>
#include <stdlib.h>
#include <sring.h>
typedef struct {
char name[10];
int height;
int weight;
} Person;
//Person형의 비교 함수 (오름차순으로 이름 정렬)
int npcmp(const Person *x, const Person *y) {
return strcmp(x->name, y->name);
}
int main(void) {
Person x[] = {
{"김영준",179,79},
{"박현규",172,63},
{"이수진",176,52},
{"최윤미",165,51},
{"함진아",181,73},
{"홍연의",172,84}
};
int nx = sizeof(x) / sizeof(x[0]);
int retry;
puts("이름으로 검색합니다.");
do {
Person temp, *p;
printf("이름 : ");
scanf("%s", temp.name);
p = bsearch(&temp, x, nx, sizeof(Person), (int*)(const void *, const void *)) npcmp);
if(p == NULL)
puts("검색에 실패했습니다");
else {
puts("검색 성공!! 아래 요소를 찾았습니다.");
printf("x[%d] : %s %dcm %dkg\n", (int)(p - x), p->name, p->height, p->weight);
}
printf("다시 검색할까요?(1) 예 / (0) 아니오 : ");
scanf("%d", &retry);
} while(retry == 1);
return 0;
}
* strcmp 반환하는 값
- x->name 쪽이 작으면 (알파벳 순서의 앞쪽이면) 음수
- x->name과 y->name이 같으면 0
- x->name 쪽이 크면 (알파벳 순서의 뒤쪽이면) 양수
'Algorithm' 카테고리의 다른 글
| 04. 스택과 큐 (0) | 2023.03.31 |
|---|---|
| [백준] 2587(대표값2) c언어 (0) | 2023.03.25 |
| [백준] 2566(최댓값) c언어 (0) | 2023.03.18 |
| [백준] 2738(행렬 덧셈) c언어 (0) | 2023.03.13 |
| [백준] 10810(공 넣기) c언어 (0) | 2023.03.06 |
'Algorithm' Related Articles
more
