03-1 검색 알고리즘
검색과 키
: 키 값을 조건에 맞게 지정해서 검색한다.
데이터 추가 비용이 많이 드는 경우 : 배열은 검색은 빠르지만 데이터를 추가하기 위한 비용이 많이 든다.
03-2 선형 검색
선형 검색
: 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘 = 순차 검색
실습 3-1
#include <iostream>
using namespace std;
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=new int;
cout << "선형 검색" << endl << "요소 개수 : " ;
cin >> nx;
*x=sizeof(int);
for(i=0;i<nx;i++){
cout << "x[" <<i<<"] : ";
cin >> x[i];
}
cout << "검색값 : ";
cin >> ky;
idx=search(x,nx,ky);
if(idx==-1)
cout << "검색에 실패했습니다. ";
else cout << ky << "는 x[" <<idx << "]에 있습니다. " <<endl;
delete x;
return 0;
}
실습 3-2
> 1의 while문을 for문으로 수정한 프로그램이다.
int search(const int a[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (a[i] == key)
return i;
return -1;
}
보초법
: 선형 검색은 무조건 두 개의 종료 조건(검색값 발견, 발견x)이 필요한데, 이는 비용이 많이 든다.
이 문제점을 해결할 수 있는 것이 바로 보초법이다.
> 검색하고자 하는 값을 배열의 마지막에 두어서 종료조건을 1개로 줄이는 방법
실습 3-3
#include <iostream>
using namespace std;
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=new int[nx+1];
cout <<"선형 검색(보초법)" <<endl
<< "요소의 개수 : ";
cin >> nx;
for (i = 0; i < nx; i++) {
cout << "x[" <<i<<"] : ";
cin >> x[i];
}
cout << "검색 값 : ";
cin >> ky;
idx = search(x, nx, ky);
if (idx == -1)
cout << "검색에 실패했습니다.";
else
cout << ky << "(은)는 x[" <<idx<<"]에 있습니다. "<<endl;
delete []x;
return 0;
}
> c언어에서의 calloc어쩌구를 c++에서는 한 줄로 요약이 가능하다.
즉, 동적할당할 배열을 초기 선언할때 =new int를 적어주어서 int형 배열이라는 것을 알려주고,
[]안에 nx+1을 넣어주어서 nx+1개 만큼의 배열을 동적할당 할 것이라는 것을 알려준다.
> 검색값 key를 보초로 a[n]에 대입했다.
> 찾은 값이 보초인지 아닌지를 구분하기 위한 if문을 추가해주어야 한다.
03-3 이진 검색
이진 검색 : 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
중앙 요소에서부터 검색을 시작해서 구간을 줄여나가는 방법
> pl=0/ pc=중앙 인덱스/pr=n-1(끝값)
> a[pc] < key
: pl의 값을 pc+1로 업데이트
> a[pc] > key
: pr의 값을 pc-1로 업데이트
> 종료조건 : 일치/ 검색범위가 없을 경우
실습 3-4
#include <iostream>
using namespace std;
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=new int[nx];
cout <<"이진 검색" <<endl
<< "요소의 개수 : ";
cin >> nx;
cout <<"오름차순으로 입력하세요.\n";
cout <<"x[0] : ";
cin >> x[0];
for (i = 1; i < nx; i++) {
do {
cout << "x[" <<i<<"] : ";
cin >> x[i];
} while (x[i] < x[i - 1]);
}
cout << "검색 값 : ";
cin >> ky;
idx = bin_search(x, nx, ky);
if (idx == -1)
puts("검색에 실패했습니다.");
else
cout << ky <<"는(은) x[" <<idx << "]에 있습니다.\n";
delete []x;
return 0;
}
복잡도
: 알고리즘의 성능을 객관적으로 평가하는 기준 (시간 복잡도/ 공간 복잡도)
연습문제 1
#include <iostream>
using namespace std;
int search(int a[], int n, int key)
{
int i = 0;
a[n] = key; //보초를 추가한다.
for(;i<n;i++){
if(a[i]==key) break;
}
return i == n ? -1 : i;
}
int main(void)
{
int i, nx, ky, idx;
int *x=new int[nx+1];
cout <<"선형 검색(보초법)" <<endl
<< "요소의 개수 : ";
cin >> nx;
for (i = 0; i < nx; i++) {
cout << "x[" <<i<<"] : ";
cin >> x[i];
}
cout << "검색 값 : ";
cin >> ky;
idx = search(x, nx, ky);
if (idx == -1)
cout << "검색에 실패했습니다.";
else
cout << ky << "(은)는 x[" <<idx<<"]에 있습니다. "<<endl;
delete []x;
return 0;
}
연습문제2 >> 하다가 잠깐 다른거 먼저
#include <iostream>
using namespace std;
int search(int a[], int n, int key)
{
int i=0;
// a[n] = key; //보초를 추가한다.
cout << " |";
for(i=0;i<n;i++) cout << " i";
cout << "---+--------------------------------------------" <<endl;
for(i=0;i<n;i++){
cout << " |";
for(int j=0;j<i+1;j++)
for(int t=0;;t++) cout << " ";
if(a[i]==key) break;
}
return i == n ? -1 : i;
}
int main(void)
{
int i, nx, ky, idx;
int *x=new int[nx+1];
cout <<"선형 검색" <<endl
<< "요소의 개수 : ";
cin >> nx;
for (i = 0; i < nx; i++) {
cout << "x[" <<i<<"] : ";
cin >> x[i];
} //값을 입력받고
cout << "검색 값 : ";
cin >> ky; //검색값을 입력받고
idx = search(x, nx, ky);
if (idx == -1)
cout << "검색에 실패했습니다.";
else
cout << ky << "(은)는 x[" <<idx<<"]에 있습니다. "<<endl;
delete []x;
return 0;
}
연습문제3
#include <iostream>
using namespace std;
int search(int a[], int b[], int n, int key)
{
int i=0; int count=0;
for(i=0;i<n;i++){
if(a[i]==key)
{for(int j=0;j<n;j++) b[j]=i; count++;}
}
return count;
}
int main(void)
{
int i, nx, ky, idx;
int *x=new int[nx+1];
int *y=new int[nx+1] ;
cout <<"이진 검색" <<endl
<< "요소의 개수 : ";
cin >> nx;
for (i = 0; i < nx; i++) {
cout << "x[" <<i<<"] : ";
cin >> x[i];
} //값을 입력받고
cout << "검색 값 : ";
cin >> ky; //검색값을 입력받고
idx = search(x, y, nx, ky);
if (idx == 0)
cout << "검색에 실패했습니다.";
else
cout << "일치하는 요소의 개수는 " << idx << "입니다. ";
delete []x;
delete []y;
return 0;
}
>> 일치하는 요소의 개수를 따로 count하는 것이 포인트다.
연습문제 4
연습문제 5
bsearch 함수
: 정렬된 배열에서 검색하는 함수
> #include <stdlib.h> 헤더 포함
> void *bsearch(const void *key, //검색값에 대한 포인터
const void *base, //배열
size_t nmemb, //요소의 개수
size_t size, //요소의 크기
int(*compar)(const void *, const void*)); //비교 함수
실습 3-5
bsearch함수는 c++에서 지원이 안되나??
실습 3C-1
'자료구조' 카테고리의 다른 글
[Do it 자료구조] 4단원 스택과 큐 c++로 풀기 (0) | 2021.03.07 |
---|---|
[Do it 자료구조] 2. 기본 자료구조 C++로 풀기 (0) | 2021.02.26 |
[Do it 자료구조] 1단원 연습문제 c++로 풀기 (0) | 2021.02.25 |
[스터디 준비] 2. 기본 자료구조 (0) | 2021.02.18 |
[스터디 준비] 01. 기본 알고리즘 정리 (0) | 2021.02.18 |