자료구조와 알고리즘 03 / (01~06)

Write Date : 2021.6.18
Last Edit : 2021.6.20

Last Page : 117page (117page 실습 3-5 작성중.)

Q1

// Q1_보초법을 사용한 검색 함수를 
// while문이 아닌 for문을 사용한 프로그램을 작성하시오

// 선형 검색(보초법)
#include <stdio.h>
#include <stdlib.h>

// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법)
int search(int a[], int n, int key)
{
    int i;
    i = 0;
    a[n] = key; // 보초를 추가
    // while (1)
    // {
    //     if(a[i] == key)
    //         break;
    //     i++;
    // }
    // return i == n ? -1 : i;
    for (i = 0; i < n; i++)
    {
        if (a[i] == key)
            return i;
    }
    return -1;
}

int main()
{
    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;
}

Q2

// Q2_선형 검색의 스캐닝 가정을 상세히 표시하는 프로그램을 작성하시오. 
// 이때 각 행의 맨 왼쪽에 있는 현재 검색하는 요소의 인덱스를 표시하고,
// 현재 검색하고 있는 요소 위에 별표 기호 *를 표시하세요.

// 선형 검색(보초법)
#include <stdio.h>
#include <stdlib.h>

// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법)
int search(int a[], int n, int key)
{
    int i, j;
    i = 0;
    j = 0;
    a[n] = key; // 보초를 추가
    printf("  |"); 
    for (i = 0; i < n; i++)
        printf("%2d", i);
    printf("\n--+----------------\n");
    for (i = 0; i < n; i++)
    {
        printf("  | ");
        for (j = 0; j < i; j++)
        {
            printf("  ");
        }
        printf("*\n");
        printf("%d |", i);
        for (j = 0; j < n; j++)
        {
             printf("%2d", a[j]);
        }
        printf("\n");
        if (a[i] == key)
            return i;
    }
    return -1;
}

int main()
{
    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;
}

Q3

// Q3_요소의 개수가 n인 배열 a에서 key와 일치하는
// 모든 요소의 인덱스를 배열 idx의 맨 앞부터 저장하고, 일치하는 요소의 개수를
// 반환하는 함수를 작성하시오.

// 예를들어, 요소의 개수가 8인 배열 a의 요소가 {1, 9, 2, 9, 4, 6, 7, 9,}이고
// 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 i, j;
    i = 0;
    j = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] == key)
        {
            idx[j++] = i;
        }
    }
    
    if (j == 0)
        return -1;
    else
        return j;
}


int main()
{
    int i, nx, ky, num;
    int *x, *idx;

    printf("요소의 갯수 : "); scanf("%d", &nx);

    x = calloc(nx, sizeof(int));
    idx = calloc(nx, sizeof(int));

    for (i = 0; i < nx; i++)
    {
        printf("x[%d] : ", i); scanf("%d", &x[i]);
    }

    printf("찾을 값 : "); scanf("%d", &ky);

    num = search_idx(x, nx, ky, idx);

    if (num == -1)
        puts("검색 실패!");
    else
    {
        printf("찾은 값은 총 %d개입니다. \n", num);
        printf("찾은 값의 위치는 {");
        for (i = 0; i < num; i++)
        {
            printf(" %d ", idx[i]);
        }
        printf("} 입니다.\n");
    }
    return 0;
}

Q4

// Q4_이진 검색의 과정을 자세히 출력하는 프로그램을 작성하시오.
// 각 행의 맨 왼쪽에 검색하고 있는 요소의 인덱스를 출력하고
// 검색 범위의 맨 앞 요소 위에 <-, 맨 끝 요소 위에 ->, 중앙 요소 위에 +를 출력하시오.

#include <stdio.h>
#include <stdlib.h>

// 요소의 개수가 n인 배열a에서 key와 일치하는 요소를 이진검색.
int bin_search(const int a[], int n, int key)
{
    int i, j;
    int pl, pr, pc; 
    // pl : 검색 범위 맨앞의 인덱스 , pr : 검색 범위 맨 끝의 인덱스
    // pc : 검색 범위 중앙의 인덱스
    pl = 0;
    pr = n - 1;

    printf("  |");
    for (i = 0; i < n; i++)
        printf("%3d", i);
    printf("\n--+-------------------------\n");
    do
    {   
        pc = (pl + pr) / 2;
        
        printf("   |");
        for(i = 0; i < pl; i++)
        {
            printf("   ");
        }
        printf(" <-");
        for(i = pl; i < pc; i++)
        {
            printf("   ");
        }
        printf(" +");
        for(i = pc; i < pr; i++)
        { 
            printf("   ");
        }
        printf(" ->\n");

        printf("%3d|", pc);
        for (i = 0; i < n; i++)
            printf("%3d", a[i]);
        printf("\n");

        if (a[pc] == key)
            return pc; // 검색 성공시 pc의 인덱스를 반환한다.
        else if (a[pc] < key)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while (pl <= pr);

    return -1; // 검색 실패시.
}


int main()
{
    int i, nx, ky, idx;
    int *x;
    printf("요소의 개수 : "); scanf("%d", &nx);
    x = calloc(nx, sizeof(int));
    puts("오름차순으로 입력하세요.");
    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)
        printf("검색 실패 !\n");
    else
        printf("%d는 x[%d]에 있습니다.\n", ky, idx);
    
    free(x);

    return 0;
}

Q5

// Q5_우리가 살펴본 이진 검색 알고리즘 프로그램은
// 검색할 값과 같은 값을 갖는 요소가 하나 이상일 경우 그 요소 중에서
// 맨 앞의 요소를 찾지 못합니다. 
// 맨 앞의 요소를 찾는 bin_search2 함수를 작성해보세요.

// 이진 검색 알고리즘에 의해 검색에 성공했을 때 그 위치로부터 앞쪽으로 하나씩
// 검사하면 여러 요소가 일치하는 경우에도 가장 앞쪽에 위치하는 요소의 인덱스를 찾아냅니다.

#include <stdio.h>
#include <stdlib.h>

int bin_search2(const int a[], int n, int key)
{
    int pl, pr, pc; 
    // pl : 검색 범위 맨앞의 인덱스 , pr : 검색 범위 맨 끝의 인덱스
    // pc : 검색 범위 중앙의 인덱스
    pl = 0;
    pr = n - 1;

    do
    {
        pc = (pl + pr) / 2;
        if (a[pc] == key)
        // return pc; // 검색 성공시 pc의 인덱스를 반환한다.
        {

            while (--pc >= 0)
            {
                if (a[pc] != key)
                    break;
            } return ++pc; // 탈출시 원하는 pc값보다 1개 작은값이기에 ++pc;
        }
        else if (a[pc] < key)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while (pl <= pr);

    return -1; // 검색 실패시.    

}


int main()
{
    int i, nx, ky, idx;
    int *x;
    printf("요소의 개수 : "); scanf("%d", &nx);
    x = calloc(nx, sizeof(int));
    puts("오름차순으로 입력하세요.");
    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_search2(x, nx, ky);

    if (idx == -1)
        printf("검색 실패 !\n");
    else
        printf("%d는 x[%d]에 있습니다.\n", ky, idx);
    
    free(x);

    return 0;
      
}
// 문제에서 주어진 정답 함수 ( pc값을 pl값과 비교하면서 처리함. )
///*--- 요솟수 n인 배열 a에서 key와 일치하는 요소를 2진 검색 (가장 앞쪽에 있는 요소를 검색) ---*/
//int bin_search2(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) {		/* 검색 성공 */
//			while (pc > pl && a[pc - 1] == key)
//				pc--;
//			return pc;
//		}
//		else if (a[pc] < key)
//			pl = pc + 1;
//		else
//			pr = pc - 1;
//	} while (pl <= pr);
//
//	return -1;					/* 검색 실패 */
//} 

검색과 키

/*1. 국적이 일본인 사람을찾는다
  2. 나이가 21세이상 27세 미만인 사람을 찾는다.
  3. 어떤 낱말과 발음이 가장 비슷한 이름의 사람을 찾는다.
*/

어떤 검색을 하게 되더라도 특정 항목에 주목한다는 점은 '검색하기'의 공통점이다.
여기서는 그 주목하는 항목을 Key(키)라고 한다. 국적을 검색하는 경우 국적이 Key(키)이며
나이를 검색하는 경우는 나이가 Key(키)이다. 데이터가 단순한 정수 값이면 데이터 값을 키 값이라고 생각해도 좋지만 대부분의 경우에는 키는 데이터의 '일부'이다.

/*1. 키 값과 일치하도록 지정한다 (한국)
  2. 키 값의 구간을 지정한다 (21세 이상 27세 미만)
  3. 키 값과 비슷하도록 지정한다 (발음이 가장 비슷한 이름).
*/

이러 조건은 하나만 지정하기도 하지만 &&나 ||를 사용하여 복합해서 지정하기도 한다.

Chap 3에서 학습하는 내용은 배열 검색이며 구체적으로 다음의 알고리즘을 활용한다.

1. 선형검색

• 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.

2. 이진검색

• 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.

3. 해시법

• 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다
  체인법
  • 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
    오픈 주소법
  • 데이터를 위한 해시 값이 충돌할 때 재해시 하는방법.

선형검색
요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색또는 순차 검색이라는 알고리즘이다.

즉 배열 검색의 종료 조건은 2개이다
1. 검색할 값을 발견하지 못하고 배열의 끝을 지난경우
2. 검색할 값과 같은 요소를 발견한 경우

무한루프
ssearch1의 While문은 '무한 루프' 구조를 사용했다.
break문이나 return문을 사용하면 루프에서 빠져나올수 있다. 무한 루프는 아래와 같이 구현된다

while(1)
{
	something...
}

for(; ;)
{
	something...
}
do
{
	something...
}while(1);

다만 끝까지 읽지 않으면 무한루프인지 아닌지 알 수 없는 do문의 무한 루프 구현은 권장하지 않는다.

보초법
선형 검색은 반복할 때마다 다음의 종료조건 (1)과 (2)를 모두 체크한다. 단순한 판단이라고 생각할 수 있지만. '티끌 모아 태산'이라는 말이 있듯이 종료 조건을 검사하는 비용은 결코 무시할 수 없다.
보초법을 사용하게 된다면
1. 검색할 값을 발견하지 못하고 배열의 끝을 지난경우
2. 검색할 값과 같은 요소를 발견한 경우
배열 검사 종료의 조건중 (1)이 없어도 된다.

이진검색
이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다
-> 정렬된 배열에서만 검색이 가능하다

이진검색의 종료 조건은 (1), (2)중 하나만 성립하면 종료가 된다.

// 검색 범위의 맨 앞 인덱스를 pl
// 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정한다.
// 검색 시작시 pl = 0, pr = n - 1, pc = (pl + pr) / 2이다. 
/* 
	1. a[pc]와 Key가 일치하는 경우
    2. 검색 범위가 더 이상 없는 경우
*/

복잡도
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라집니다.
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 합니다. 복잡도는 아래의 두 가지 요소를 가지고 있습니다.

 /*
 1. 시간 복잡도 : 실행에 필요한 시간을 평가한것.
 2. 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한것. 
 */

bsearch 함수 ( 정렬된 배열에서 검색하는 함수 )
c언어의 표준 라이브러리는 다양한 요소의 자료형을 가진 배열에서도 검색 가능한 bsearch함수를 제공합니다. 이 함수를 일반 유틸리티 함수라고 부릅니다.

/*
	1. 검색 대상의 배열은 항상 정렬되어 있어야한다.
    2. 검색하는 값과 같은 요소가 여러개 존재하는 경우, 항상 가장 앞쪽에 있는 요소를 찾아내		  는건 아니다.
    
    void *besearch(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객체와 비교가 가능한 작은 요소, 같은요소, 큰 요소의 세 부분으로 구성되어 있습니다. 이 세부분이 소개한 순서로 잰재해야합니다.
    
    1. 첫 번째 인수로 전달하는 매개변수는 키값입니다 (검색할 값이 젖아된 객체애 대한 포인터).
    2. 두 번째 인수로 전달하는 매개변수는 배열의 포인터입니다.
    3. 세 번째 인수로 전달하는 매개변수는 배열의 요소 개수입니다.
    4. 네 번재 인수로 전달하는 매개변수는 배열의 요소 크기입니다.
    5. 가장 복잡한 것이 다섯 번째 인수입니다.
*/