공부할 책 : 자료구조와 함께 배우는 알고리즘 입문 - C언어 편
검색 알고리즘
어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 다양하게 존재하는 경우에는 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 한다.
선형 검색
요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색 또는 순차 검색이라는 알고리즘이다.
배열 검색의 종료 조건은 2개이다.
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 - 검색 실패
- 검색할 값과 같은 요소를 발견할 경우 - 검색 성공
실습 코드 1 :
/* 선형 검색 */
#include <stdio.h>
#include <stdlib.h>
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색 ---*/
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++;
}
}
int main() {
int i, nx, ky, idx;
int* x;
puts("선형 검색");
printf("요소 개수 : ");
scanf_s("%d", &nx);
x = (int*)calloc(nx, sizeof(int));
for (i = 0;i < nx;i++) {
printf("x[%d] : ", i);
scanf_s("%d", &x[i]);
}
printf("검색값 : ");
scanf_s("%d", &ky);
idx = search(x, nx, ky);
if (idx == -1) puts("검색에 실패했습니다.");
else printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}보초법
선형 검색은 반복할 때마다 종료 조건 1,2를 모두 체크한다.
종료 조건을 검사하는 비용은 결코 무시할 수 없다.
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 - 검색 실패
- 검색할 값과 같은 요소를 발견할 경우 - 검색 성공
이 비용을 반으로 줄이는 방법이 보초법이다.
a[0]~a[6]에 데이터가 있으면 검색하기 전에 검색하고자 하는 키 값을 맨 끝 a[7]에 저장한다. 이때 저장하는 값을 보초라고 한다.
다음 코드는 위의 실습 코드 1을 수정한 코드이다.
실습 코드 2 :
/* 선형 검색(보초법) */
#include <stdio.h>
#include <stdlib.h>
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법) ---*/
int search(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;
}
int main(void)
{
int i, nx, ky, idx;
int* x;
puts("선형 검색(보초법)");
printf("요소 개수 : ");
scanf_s("%d", &nx);
x = (int*)calloc(nx + 1, sizeof(int));
for (i = 0;i < nx;i++) {
printf("%x[%d] : ", );
scanf_s("%d", &x[i]);
}
printf("검색값 : ");
scanf_s("%d", &ky);
idx = search(x, nx, ky);
if (idx == -1)
puts("검색에 실패하였습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}이진 검색
이 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬되어 있다는 것이다. 이진 검색은선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.
/* 선형 검색(보초법) */
#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) pr = pc - 1;
else if (a[pc] < key) pl = pc + 1;
} while (pr >= pl);
return -1;
}
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법) ---*/
int main(){
int i, nx, ky, idx;
int* x;
puts("이진 검색");
printf("요소 개수 : ");
scanf_s("%d", &nx);
x = (int*)calloc(nx, sizeof(int));
printf("오름차순으로 입력하세요.\n");
printf("x[0] : ");
scanf_s("%d", &x[0]);
for (i = 1;i < nx;i++) {
do {
printf("x[%d] : ", i);
scanf_s("%d", &x[i]);
} while (x[i] < x[i - 1]);
}
printf("검색값 : ");
scanf_s("%d", &ky);
idx = bin_search(x, nx, ky);
if (idx == -1) puts("검색에 실패했습니다.");
else printf("%d는(은) x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}복잡도
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다.
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다.
복잡도는 아래의 두 가지 요소를 가지고 있다.
시간 복잡도 - 실행에 필요한 시간을 평가한 것
공간 복잡도 - 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
한 번만 실행하는 경우 복잡도는 O(1) 로 표기한다.
실행횟수 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)이라고 표기한다.
여기서 컴퓨터에게 n/2 와 n 의 차이는 사람이 느낄 수 없을 정도로 굉장히 작다.
일반적으로 O(f(n))과 O(g(n))의 복잡도를 계산하는 방법은 아래와 같다.
2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시한다.
O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
이진 검색 알고리즘의 복잡도는 O(log n) 과 같다.
연습문제
Q3. 요소의 개수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장하고, 일치한 요소의 개수를 반환하는 함수를 작성하세요. 예를 들어 요소의 개수가 8인 배열 a의 요소가 {1,9,2,9,4,6,7} 이고 key가 9이면 배열 idx에 {1,3,7}을 저장하고 3을 반환한다.
#include <stdio.h>
#include <stdlib.h>
int search_idx(const int a[], int n, int key, int idx[]) {
int ptr=0;
for (int i = 0;i < n;i++) {
if (a[i] == key) {
idx[ptr++] = i;
}
}
return ptr;
}
int main() {
int cnt = 0, num1,num2,idx;
printf("배열 요소수 입력 : ");
scanf_s("%d", &num1);
int* arr1 = (int*)calloc(num1, sizeof(int));
for (int i = 0;i < num1;i++) {
printf("arr1[%d] : ", i);
scanf_s("%d", &arr1[i]);
}
printf("찾을 값 입력 : ");
scanf_s("%d", &num2);
for (int i = 0;i < num1;i++) {
if (arr1[i] == num2) {
cnt++;
}
}
int* arr2 = (int*)calloc(cnt, sizeof(int));
idx = search_idx(arr1, num1, num2, arr2);
printf("찾을 값 개수 : %d\n찾을 값 인덱스 : ", idx);
for (int i = 0;i < cnt;i++) {
printf("%d ", arr2[i]);
}
}Q4. 오른쪽처럼 이진 검색의 과정을 자세히 출력하는 프로그램을 작성하세요. 각 행의 맨 왼쪽에 현재 검색하고 있는 요소의 인덱스를 출력하고 검색 범위의 맨 앞 요소 위에 <-, 맨 끝 요소 위에 ->, 현재 검색하고 있는 중앙 요소 위에 +를 출력하세요.
생략
Q5. 우리가 살펴본 이진 검색 알고리즘 프로그램은 검색할 값과 같은 값을 갖는 요소가 하나 이상일 경우 그 요소 중에서 맨 앞의 요소를 찾지 못합니다. 예를 들어 {1,3,5,7,7,7,7,8,8,9,9} 배열에서 7을 검색하면 중앙에 위치하는 a[5]를 검색한다. 맨 앞의 요소를 찾는 bin_search2 함수를 작성해 보세요.
#include <stdio.h>
#include <stdlib.h>
int bin_search2(const int a[],int key) {
int pl=0, pr=sizeof(a), pc;
do {
pc = (pl + pr) / 2;
if (a[pc] == key) return pc;
else if (a[pc] > key) pr = pc - 1;
else pl = pc + 1;
} while (pl <= pr);
return -1;
}
int main() {
int arr[11] = { 1,3,5,7,7,7,7,8,8,9,9 };
int num1 = 7;
int idx;
idx = bin_search2(arr, num1);
printf("%d", idx);
}bsearch 함수
정렬된 배열에서 검색하는 함수
다양한 요소의 자료형을 가진 배열에서도 검색 가능하다.
bsearch (인수1,인수2,인수3,인수4,인수5)
인수 1 - 키 값 (찾을 값)
인수 2 - 배열의 포인터
인수 3 - 배열의 요소 개수
인수 4 - 배열의 요소 크기
인수 5 - 비교 함수
실습 예제 :
#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;
}
int main() {
int i, nx, ky;
int* x;
int* p;
puts("bsearch 함수를 사용하여 검색");
printf("요소 개수 : ");
scanf_s("%d", &nx);
x = (int*)calloc(nx, sizeof(int));
printf("오름차순으로 입력하세요.\n");
printf("x[0] : ");
scanf_s("%d", &x[0]);
for (i = 1;i < nx;i++) {
do {
printf("x[%d] : ", i);
scanf_s("%d", &x[i]);
} while (x[i] < x[i - 1]);
}
printf("검색값 : ");
scanf_s("%d", &ky);
p = (int*)bsearch(&ky,
x,
nx,
sizeof(int),
(int(*)(const void*, const void*)) int_cmp
);
if (p == NULL)
puts("검색에 실패하였습니다.");
else
printf("%d는 x[%d]에 있습니다.", ky, p-x);
}비교 함수
이때 '인수5' 에 대한 설명이다.
이진 검색의 검색 과정에는 검색하는 키 값과 배열의 요솟값을 비교하여 대소 관계를 판단하는 과정이 포함된다. 그런데 대소 관계를 판단하는 방법은 요소의 자료형마다 다르다. 요소의 자료형은 정수일 수도 있고 문자열이나 구조체일 수도 있다. 그러므로 두 값을 비교하고 난 다음의 어떤 값을 반환하는 비교 함수는 사용자가 직접 작성해야 한다.
따라서 bsearch 함수는 다섯 번째 매개변수로 이 비교함수에 대한 포인터를 전달하는 방식을 취하고 있다.
함수 포인터
이름 그대로 함수를 가리키는 포인터
함수 포인터의 자료형은 가리키는 함수에 따라 다르다.
실습 예제 :
/* 덧셈표와 곱셈표 */
#include <stdio.h>
/*--- x1과 x2의 합을 구합니다. ---*/
int sum(int x1, int x2)
{
return x1 + x2;
}
/*--- x1과 x2의 곱을 구합니다. ---*/
int mul(int x1, int x2)
{
return x1 * x2;
}
/*--- 덧셈, 곱셈표를 출력 ---*/
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');
}
}
int main(void)
{
puts("덧셈표");
kuku(sum);
puts("\n 곱셈표");
kuku(mul);
return 0;
}호출된 kuku 함수는 sum함수에 대한 포인터를 매개변수 calc로 받아들인다.
받아들인 함수에 대한 포인터를 사용하는 코드는 (*calc)(i,j)이다.
간접 연산자 *를 적용한 코드를 실행하면 그 포인터가 가리키는 함수(sum)가 호출된다.
여기서 *calc를 둘러싸고 있는 ()는 생략할 수 없다. 간접 연산자 *보다 함수를 호출하는 연산자 ()쪽이 우선순위가 높기 때문이다.
kuku(mul); 에서
kuku 함수가 호출되는 경우에는 인수 calc로 받아들이는 인자의 값이 mul 함수에 대한 포인터이므로 식 (*calc)(i,j)의 실행으로 호출하는 함수는 mul 함수이다.
포인터 calc가 가리키는 함수를 호출하는 코드 ((*calc)(i,j)는 프로그램을 컴파일할 때가 아니라 실행할 때 실제로 어떤 함수를 호출할 지 결정한다.
이렇게 함수에 대한 포인터를 사용하면 호출하는 함수를 실행하여 결정하는 동적 함수 호출을 구현할 수 있다. 동적 함수 호출을 사용하면 사용자가 원하는 경우에 sum함수와 mul함수를 직접 작성하여 호출하지 않아도 실행할 수 있다.
구조체 배열에서 검색하기
실습 예제 :
/* bsearch 함수를 사용한 구조체 배열에서의 검색 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char name[10];
int height;
int weight;
} Person;
int npcmp(const Person* x, const Person* y) {
return strcmp(x->name, y->name);
}
int main() {
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("%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", p - x, p->name, p->height, p->weight);
}
printf("다시 검색할까요? (1) 예 / (0) 아니오 : ");
scanf_s("%d", &retry);
} while (retry == 1);
return 0;
}연습 문제
Q6. 요소의 값이 내림차순으로 정렬된 long형 배열엣의 검색을 bsearch 함수를 사용하여 프로그램을 작성하세요.
#include <stdio.h>
#include <stdlib.h>
int fnc(const long* a, const long* b) {
if (*a < *b) return 1;
else if (*a > *b) return -1;
else return 0;
}
int main() {
long a[10] = { 10,9,8,7,6,5,4,3,2,1 };
int search = 7;
long *idx;
idx = (long*)bsearch(&search, a, 10, sizeof(long),
(int(*)(const void *, const void *))fnc);
printf("%d", (int)(idx-a));
}Q7. bsearch 함수와 같은 형식으로 호출할 수 있는 다음 함수를 작성하세요. 단, 선형 검색 알고리즘을 사용하고, 배열은 정렬되어 있지 않아도 좋습니다.
#include <stdio.h>
#include <stdlib.h>
void* seqsearch(const void* key, const void* base, size_t nmemb, size_t size, int(*compar)(const void*, const void*)) {
char* x = (char*)base;
for (int i = 0;i < nmemb;i++) {
if (!compar(key, (const void *)&x[i*size])) {
return(&x[i*size]);
}
}
return NULL;
}
int fnc(const int *a,const int *b){
if (*a > *b) return 1;
else if (*a < *b) return -1;
else return 0;
}
int main() {
int a[] = { 1,3,2,4,6,8,4,7,6,8,10,9 };
int search = 6;
int* seq;
seq = (int*)seqsearch(&search, a, sizeof(a), sizeof(int),
(int(*)(const void*, const void*))fnc);
printf("%d", seq-a);
}Q8. bsearch 함수와 같은 형식으로 호출할 수 있는 다음 함수를 이진 검색 알고리즘을 사용하여 작성하세요.
void* binsearch(const void* key, const void* base, size_t nmemb, size_t size, int(*compar)(const void*, const void*)) {
char* x = (char*)base;
int pl = 0;
int pr = nmemb - 1;
int pc;
do {
pc = (pl + pr) / 2;
int res = compar(key, &x[pc*size]);
printf("%d ", res);
if (res == 0) return &x[pc*size];
else if (res == 1) pl = pc + 1;
else pr = pc - 1;
} while (pl < pr);
printf("실패");
return NULL;
}
int fnc(const int *a,const int *b){
if (*a < *b) return -1;
else if (*a > *b) return 1;
else return 0;
}
int main() {
int a[] = { 1,2,3,4,5,6,7,8,9,10,11 };
int search = 3;
int* seq;
seq = (int*)binsearch(&search, a, sizeof(a), sizeof(int),
(int(*)(const void*, const void*))fnc);
printf("%d", seq-a);Q9. bsearch 함수와 같은 형식으로 호출할 수 있는 다음 함수를 작성하세요. 이때 Q5처럼 이진 검색 알고리즘을 사용하여 요소의 검색에 성공하면 그 위치에서 앞쪽으로 선형 검색을 수행하여 가장 앞쪽의 요소에 대한 포인터를 변환하세요.
void* bsearchx(const void* key, const void* base, size_t nmemb, size_t size, int(*compar)(const void*, const void*)) {
char* x = (char*)base;
int pl = 0;
int pr = nmemb - 1;
int pc;
do {
pc = (pl + pr) / 2;
int res = compar(key, &x[pc * size]);
if (res == 0) {
while (1) {
if (compar(key,&x[(--pc)*size])) break;
}
return &x[(pc+1) * size];
}
else if (res == 1) pl = pc + 1;
else pr = pc - 1;
} while (pl < pr);
printf("실패");
return NULL;
}
int fnc(const int *a,const int *b){
if (*a < *b) return -1;
else if (*a > *b) return 1;
else return 0;
}
int main() {
int a[] = { 1,1,2,3,3,3,4,5,5,6,7,8 };
int search = 3;
int* seq;
seq = (int*)bsearchx(&search, a, sizeof(a), sizeof(int),
(int(*)(const void*, const void*))fnc);
printf("%d", seq-a);
}
흔한 컴공러 / 3학년