목차
검색
말 그대로 무언가를 찾는 것인데 우리가 영어 사전에서 의미가 궁금한 단어를 검색하거나, 인터넷에서 맛집을 찾을 때 검색을 한다.
이러한 검색도 정렬처럼 자료구조를 활용하는데, 자료를 만들고 저장하고 정렬하는 이유는 자료를 사용하기 위해서이고, 사용하려면 자료 중에서도 원하는 항목을 찾아야 한다. 따라서 자료를 검색하는 것은 원하는 탐색 키를 가진 항목을 찾는 것이다.
저장한 자료는 그 자료를 구별하여 인식할 수 있는 키를 가지고 있는데, 이것을 탐색 키 Search Key라고 한다.
또한 자료 속에서 원하는 자료를 찾으면 성공 Hit이라고 하며, 실패한다면 검색 실패 Miss라고 한다.
이러한 검색 연산은 삽입 연산과 삭제 연산을 할 때도 필요하다. 원소를 삽입하거나 삭제하려면 먼저 그 위치를 찾아야 하기 때문고 검색 방법의 효율성은 사용하는 자료구조와 자료의 배열 상태에 따라 달라지므 로 해결해야 하는 문제와 상황에 따라 최적의 검색 방법을 사용해야 한다.
검색은 수행되는 위치에 따라 메모리 내에서 수행하는 내부 검색 Internal Search과 메모리의 외부에 있는 보조기억 장치에서 수행하는 외부 검색 External Search으로 나눌 수 있다. 또한 검색 방법에 따라 비교 검색 Comparison Search과 계산 검색 Non-comparison Search으로 나눌 수 있다
| 검색 방법 | 설명 | 종류 |
| 비교 검색 | 검색 대상의 키를 비교하여 검색한다. | 순차 검색, 이진 검색, 트리 검색 |
| 계산 검색 | 계수적인 성질을 이용한 계산으로 검색한다. | 해싱 |
순차 검색 Sequential Search
순차 검색은 일렬로 나열된 자료를 처음부터 마지막까지 순서대로 검색하는 가장 간단한 방법으로 기본 순차 검색 Basic Sequential Search 또는 선형 검색 Linear Search이라고도 한다.
배열이나 연결 리스트로 구현된 선형 자료 구조에서 순서대로 비교하며 원하는 항목을 찾는다. 하지만 이러한 순차 방식의 검색은 검색해야 하는 자료의 양에 따라 검색 성능(효율)이 달라진다. 또한 검색해야 할 자료가 정렬된 상태인지 아닌지에 따라 검색 실패하는 시점도 달라진다. 정렬되어 있지 않은 자료를 순차 검색할 때는 처음부터 끝까지 돌아가며 키값이 일치하는 원소를 찾아서 검색해야 한다.
정렬되지 않은 자료의 순차 검색
#include <stdio.h>
typedef int element;
void sequentialSearch1(element a[], int n, element key) {
int i = 0;
printf("\n%3d를 검색하라! ->> ", key);
while (i < n && a[i] != key) i++;
if (i < n) printf("%3d번째에 검색 성공! \n", i + 1);
else printf("%3d번째에 검색 실패! \n", i + 1);
}
int main(void) {
int i;
element a[] = { 8, 30, 1, 9, 11, 19, 2 };
int size = sizeof(a)/sizeof(a[0]); //배열 원소의 개수
printf("\n\t<< 검색 대상 자료 >>\n");
for (i = 0; i < size; i++) printf("%5d", a[i]); puts("");
sequentialSearch1(a, size, 9); // 배열 a의 n개 원소 중에서 탐색키가 9인 원소 검색
sequentialSearch1(a, size, 6); // 배열 a의 n개 원소 중에서 탐색키가 6인 원소 검색
getchar(); return 0;
}
---------------------------------------
<< 검색 대상 자료 >>
8 30 1 9 11 19 2
9를 검색하라! ->> 4번째에 검색 성공!
6를 검색하라! ->> 8번째에 검색 실패!정렬된 자료의 순차 검색
#include <stdio.h>
typedef int element;
void sequentialSearch2(element a[], int n, element key) {
int i = 0;
printf("\n%3d를 검색하라! ->> ", key);
while (i < n && a[i] < key) i++;
if (a[i] == key) printf("%3d번째에 검색 성공!\n", i + 1);
else printf("%3d번째에 검색 실패! \n", i + 1);
}
int main(void) {
int i;
element a[] = { 1, 2, 8, 9, 11, 19, 29 };
int size = sizeof(a) / sizeof(a[0]); //배열 원소의 개수
printf("\n\t<< 검색 대상 자료 >>\n");
for (i = 0; i < size; i++) printf("%5d", a[i]); puts("");
sequentialSearch2(a, size, 9); // 배열 a의 n개 원소 중에서 탐색키가 9인 원소 검색
sequentialSearch2(a, size, 6); // 배열 a의 n개 원소 중에서 탐색키가 6인 원소 검색
getchar(); return 0;
}
-------------------------------------------
<< 검색 대상 자료 >>
1 2 8 9 11 19 29
9를 검색하라! ->> 4번째에 검색 성공!
6를 검색하라! ->> 3번째에 검색 실패!색인 순차 검색 Index Sequential Search
색인 순차 검색 또는 인덱스 순차 검색은 인덱스 테이블 Index Table을 사용하여 탐색의 범위를 줄여 검색 효율을 높인 방법이다.
인덱스 테이블은 배열에 정렬되어 있는 자료 중에서 일정한 간격으로 떨어져 있는 원소들을 가지고 있다. 색인 순차 검색은 정렬된 자료일 때만 사용한다. 자료가 저장되어 있는 배열의 크기가 n이고, 인덱스 테이블의 크기가 m일 때 배열에서 n/m 간격으로 떨어져 있는 원소와 원소의 인덱스를 인덱스 테이블에 저장한다.
찾고자 하는 키값을 인덱스 테이블에 서 검색하여 indexTable[i]. key <= key <= indexTable[i+1]. key를 만족하는 i를 찾아서 검색 범위를 정하고 해당 범위에 대해서만 순차 검색을 수행한다.
#include <stdio.h>
typedef int element;
#define INDEX_SIZE 3 // 인덱스 테이블의 크기를 3으로 정의
void sequentialSearch3(element a[], int begin, int end, element key);
// 인덱스 테이블의 구조(index, key)를 정의
typedef struct {
int index;
element key;
} iTable;
iTable indexTable[INDEX_SIZE]; // 인덱스 테이블 indexTable 생성
// 배열 a에 대한 인덱스 테이블 만들기
iTable* makeIndexTable(element a[], int size) {
int i, n;
n = size / INDEX_SIZE; // 인덱스 테이블에 들어가는 배열 원소의 간격 계산
if (size % INDEX_SIZE > 0) n++;
for (i = 0; i < INDEX_SIZE; i++) { // 인덱스 테이블의 채우기
indexTable[i].index = i * n;
indexTable[i].key = a[i * n];
}
return indexTable;
}
// 색인 순차 검색
void indexSearch(iTable indexTable[], element a[], int n, element key) {
int i, begin, end;
if (key < a[0] || key > a[n - 1])
printf("\n찾는 키가 없습니다. 검색 실패! \n");
// 인덱스 테이블을 검색하여 검색 범위 결정
for (i = 0; i < INDEX_SIZE; i++){
if ((indexTable[i].key <= key) && (indexTable[i + 1].key > key)) {
begin = indexTable[i].index;
end = indexTable[i + 1].index;
break;
}
if (i == INDEX_SIZE) {
begin = indexTable[i - 1].index;
end = n;
}
}
sequentialSearch3(a, begin, end, key); // 검색 범위에 대한 순차검색 수행
}
void sequentialSearch2(element a[], int n, element key) {
int i = 0;
printf("\n%3d를 검색하라! ->> ", key);
while (i < n && a[i] < key) i++;
if (a[i] == key) printf("%3d번째에 검색 성공!\n", i + 1);
else printf("%3d번째에 검색 실패! \n", i + 1);
}
void sequentialSearch3(element a[], int begin, int end, element key) {
int i = begin;
printf("\n%3d를 검색하라! ->> ", key);
while (i < end && a[i] < key) i++;
if (a[i] == key) printf("%3d번째에 검색 성공!\n", (i-begin) + 1);
else printf("%3d번째에 검색 실패! \n", (i-begin) + 1);
}
int main(void) {
element a[] = { 1, 2, 8, 9, 11, 19, 29 };
int i, size = sizeof(a) / sizeof(a[0]); //배열 원소의 개수
iTable* indexTable;
printf("\n\t<< 검색 대상 자료 >>\n");
for (i = 0; i < size; i++) printf("%5d", a[i]); puts("");
printf("\n\n\t<< 순차 검색 >>\n");
sequentialSearch2(a, size, 9); // 배열 a의 n개 원소 중에서 탐색키가 9인 원소 검색
sequentialSearch2(a, size, 6); // 배열 a의 n개 원소 중에서 탐색키가 6인 원소 검색
printf("\n\n\t<< 색인 순차 검색 >>\n");
indexTable= makeIndexTable(a, size);
indexSearch(indexTable, a, size, 9); // 배열 a의 n개 원소 중에서 탐색키가 9인 원소 검색
indexSearch(indexTable, a, size, 6); // 배열 a의 n개 원소 중에서 탐색키가 6인 원소 검색
getchar(); return 0;
}
------------------------------------------
<< 검색 대상 자료 >>
1 2 8 9 11 19 29
<< 순차 검색 >>
9를 검색하라! ->> 4번째에 검색 성공!
6를 검색하라! ->> 3번째에 검색 실패!
<< 색인 순차 검색 >>
9를 검색하라! ->> 1번째에 검색 성공!
6를 검색하라! ->> 3번째에 검색 실패!이진 검색 Binary Search
이진 검색은 자료 가운데 있는 항목을 키값과 비교하여 키값이 더 크면 오른쪽 부분을 검색하고, 키 값이 더 작으면 왼쪽 부분을 검색한다.
가운데 있는 값을 기준으로 왼쪽과 오른쪽 두 부분으로 나누어서 검색하므로 이분 검색 또는 보간 검색 Interpolaton Search이라고도 한다. 키를 찾을 때까지 이진 검색을 순환적으로 반복하여 수행함으로써 검색 범위를 반으로 줄여 가면서 빠르게 검색한다. 따라서 정렬되어 있는 자료를 검색할 때만 사용할 수 있다. 이진 검색은 검색 범위를 반으로 분할하고 검색하는 작업을 반복하므로 분할 정복 기법을 이용한 방법이다.
#include <stdio.h>
typedef int element;
int cnt=0; // 이진 검색의 연산 횟수
void binarySearch(element a[], int begin, int end, element key) {
int middle;
cnt++; // 이진 검색 연산 횟수 1 증가
if (begin == end) { // 검색 범위가 한 개인 경우
if (key == a[begin]) printf("%3d번째에 검색 성공!\n", cnt);
else printf("%3d번째에 검색 실패! \n", cnt);
return;
}
middle = (begin + end) / 2; // 검색 범위가 이진 분할되는 기준 위치 설정
if (key == a[middle]) printf("%3d번째에 검색 성공!\n", cnt);
else if (key < a[middle] && (middle - 1 >= begin))
binarySearch(a, begin, middle - 1, key);
else if (key > a[middle] && (middle + 1 <= end))
binarySearch(a, middle + 1, end, key);
else printf("%3d번째에 검색 실패! \n", cnt);
}
int main(void) {
element a[] = { 1, 2, 8, 9, 11, 19, 29 }, key;
int i, size = sizeof(a) / sizeof(a[0]); //배열 원소의 개수
char more;
extern int cnt;
printf("\n\t<< 검색 대상 자료 >>\n");
for (i = 0; i < size; i++) printf("%5d", a[i]); puts("");
do {
cnt = 0;
printf("\n\n검색할 키를 입력하세요 : "); scanf("%d", &key);
printf("\n%3d를 검색하라! ->> ", key);
binarySearch(a, 0, size - 1, key);
printf("\n\n검색을 계속하려면 y를 누르세요>> "); scanf(" %c", &more);
} while ( more == 'y');
getchar(); return 0;
}
--------------------------------------
<< 검색 대상 자료 >>
1 2 8 9 11 19 29
검색할 키를 입력하세요 : 29
29를 검색하라! ->> 3번째에 검색 성공!
검색을 계속하려면 y를 누르세요>> y
검색할 키를 입력하세요 : 8
8를 검색하라! ->> 3번째에 검색 성공!이진트리 검색 Binary Tree Search
이진 트리 검색은 루트 노드를 기준으로 왼쪽 서브 트리는 루트 노드보다 키값이 작은 원소로 구성이 되고 오른쪽 서브 트리는 루트 노드보다 키값이 큰 원소로 구성되는 특징을 이용한다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_WORD_LENGTH 20 // 영어 사전에 들어갈 단어 길이를 20으로 정의
#define MAX_MEAN_LENGTH 200 // 영어 사전에 들어갈 단어 뜻의 길이를 200으로 정의
// 영어 사전 항목의 구조 정의
typedef struct {
char word[MAX_WORD_LENGTH];
char mean[MAX_MEAN_LENGTH];
}element;
// 영어 사전 이진 트리의 노드 구조 정의
typedef struct treeNode {
element key;
struct treeNode* left;
struct treeNode* right;
}treeNode;
// << 이진 탐색 트리 연산 수행 : [예제 7-4] 참고 >>
// 포인터 p가 가리키는 노드와 비교하여 항목 key를 삽입하는 연산([예제 7-4] 참고)
treeNode* insertKey(treeNode* p, element key) {
treeNode* newNode;
int compare;
// 삽입할 자리에 새 노드를 구성하여 연결
if (p == NULL) {
newNode = (treeNode*)malloc(sizeof(treeNode));
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 이진 트리에서 삽입할 자리 탐색
else {
compare = strcmp(key.word, p->key.word);
if (compare < 0) p->left = insertKey(p->left, key);
else if (compare > 0) p->right = insertKey(p->right, key);
else printf("\n 이미 같은 단어가 있습니다! \n");
return p; // 삽입한 자리 반환
}
}
void insertWord(treeNode** root, element key) {
*root = insertKey(*root, key);
}
// root 노드부터 탐색하여 key와 같은 노드를 찾아 삭제하는 연산
void deleteWord(treeNode* root, element key) {
treeNode* parent, * p, * succ, * succ_parent;
treeNode* child;
parent = NULL;
p = root;
while ((p != NULL) && (strcmp(p->key.word, key.word) != 0)) {
parent = p;
if (strcmp(key.word, p->key.word) < 0) p = p->left;
else p = p->right;
}
// 삭제할 노드가 없는 경우
if (p == NULL) {
printf("\n 삭제할 단어가 사전에 없습니다!!");
return;
}
// 삭제할 노드가 단말 노드인 경우
if ((p->left == NULL) && (p->right == NULL)) {
if (parent != NULL) {
if (parent->left == p) parent->left = NULL;
else parent->right = NULL;
}
else root = NULL;
}
// 삭제할 노드가 자식 노드를 한 개 가진 경우
else if ((p->left == NULL) || (p->right == NULL)) {
if (p->left != NULL) child = p->left;
else child = p->right;
if (parent != NULL) {
if (parent->left == p) parent->left = child;
else parent->right = child;
}
else root = child;
}
// 삭제할 노드가 자식 노드를 두 개 가진 경우
else {
succ_parent = p;
succ = p->right;
while (succ->left != NULL) {
succ_parent = succ;
succ = succ->left;
}
if (succ_parent->left == succ)
succ_parent->left = succ->right;
else succ_parent->right = succ->right;
p->key = succ->key;
p = succ;
}
free(p);
}
// 이진 탐색 트리에서 키값이 key인 노드 위치를 탐색하는 연산
treeNode* searchDic(treeNode* root, element key) {
treeNode* p;
int compare;
p = root;
while (p != NULL) {
compare = strcmp(key.word, p->key.word);
if (compare < 0) p = p->left;
else if (compare > 0) p = p->right;
else {
printf("\n찾은 단어 : %s", p->key.word);
return p;
}
}
return p;
}
// 이진 탐색 트리를 중위 순회하면서 출력하는 연산
void displayDic(treeNode* root) {
if (root) {
displayDic(root->left);
printf("\n%s : %s", root->key.word, root->key.mean);
displayDic(root->right);
}
}
// 영어 사전 메뉴
void menu() {
printf("\n*---------------------------*");
printf("\n\t1 : 출력");
printf("\n\t2 : 입력");
printf("\n\t3 : 삭제");
printf("\n\t4 : 검색");
printf("\n\t5 : 종료");
printf("\n*---------------------------*\n ");
}
int main(void) {
int choice;
element e;
treeNode* dic = NULL, * temp = NULL;
// [5 :종료] 메뉴를 선택할 때까지 메뉴에 대한 영어 사전 동작 반복
do {
menu(); printf("메뉴를 선택하세요 : ");
scanf("%d", &choice); rewind(stdin);
switch (choice) {
case 1:
printf("\t[사전 출력]");
displayDic(dic); printf("\n\t[사전 끝]\n");
break;
case 2:
printf("\n[단어 입력] 단어를 입력하시오 : "); gets(e.word);
printf("\n[단어입력] 단어의 뜻을 입력하시오 : "); gets(e.mean);
insertWord(&dic, e);
break;
case 3:
printf("\n[단어 삭제] 삭제할 단어 : "); gets(e.word);
deleteWord(dic, e);
break;
case 4:
printf("\n[단어 검색] 검색할 단어 : ");
gets(e.word);
temp = searchDic(dic, e);
if (temp != NULL)
printf("\n단어 뜻 : %s", temp->key.mean);
else printf("\n사전에 없는 단어입니다.");
break;
case 5: break;
default: printf("\n없는 메뉴입니다. 다시 선택해주세요!\n");
}
} while (choice != 5);
getchar(); return 0;
}
---------------------------------------------------해싱은 다음 포스트에....
'알고리즘' 카테고리의 다른 글
| [알고리즘] 검색 2 - 해싱 + 단어 사전 프로그램 (1) | 2023.12.09 |
|---|---|
| [알고리즘] 정렬 6 - 히프 정렬 Heap Srot, 트리 정렬 Tree Sort (0) | 2023.12.09 |
| [알고리즘] 정렬 5 - 기수 정렬 Radix Sort (0) | 2023.12.09 |
| [알고리즘] 정렬 4 - 병합 정렬(2-way, n-way) (0) | 2023.12.09 |
| [알고리즘] 정렬 3 - 삽입정렬, 셸 정렬 (0) | 2023.12.09 |