Programming/C C++
1. 선형탐색

선형탐색이란 아주 고전적이고 단순한 형태의 Data탐색 방법으로 처음부터 하나씩 순차적으로 비교해 가면서 원하는 Data를 찾는 방식입니다. 이와 같은 선형탐색에 주로 사용되는 함수로는 lfind와 lsearch가 있습니다.

#include <stdio.h>
#include <search.h>
#include <string.h>

int _strcmp(const void *a, const void *b);

main()
{
  char s[3][6] = {"abcde", "fghij", "klmno"};
  char ss[6] = "fghij";
  char *p;
  int datanum = 3;
 
  p = (char *)lfind(ss, s, &datanum, 6, _strcmp);
 
  printf("%s\n", p);
  printf("%d\n", datanum);
}

int _strcmp(const void *a, const void *b)
{
  return strcmp((char *)a, (char *)b);
}


lfind()함수를 통해 "fghij" 라는 Data를 s배열에서 찾도록 합니다.

Program의 Header 선언부분에 search.h는 lfind()함수를, string.h는 strcmp()함수사용을 위해 선언되었습니다.

lfind()함수를 사용하기 위해 우선 선형검색의 대상이 될 배열을 정의합니다. 배열은 Data구조의 기본이며 이는 C언어 뿐만 아니라 다른 언어에서도 마찬가지 입니다.

배열은 s배열을 [3][6]으로 하여 2차원 배열로 선언한뒤 해당 배열에 3개의 문자열을 초기화 합니다. 이로 인해 s[0]에는 "abcde", s[1]에는 "fghij", s[2]에는 "klmno"의 문자열이 저장됩니다. (문자열은 문자열끝을 0(\0)으로 판단하므로 배열의 크기를 정할때 이부분을 감안하도록 하였습니다.)

Pointer p는 lfind()함수에서 결과값을 받기 위한 Pointer이며 datanum은 선형검색을 수행하기 위해 배열의 크기를 정의한 변수입니다.

lfind()의 첫번째 인수로는 찾고자 하는 Data의 Pointer를 건네줘야 합니다. 단, 변수를 통하지 않고 다음처럼 직접 값을 전달해 줄 수도 있습니다.

lfind("fghij", s, &datanum, 6, _strcmp);

lfind()함수의 두번째 인수는 선형검색을 수행할 배열을 지정하며 세번째 인수는 배열의 크기값을 가진 변수의 주소를 그리고 네번째 인수는 배열에서 비교할 각 Data의 크기값을 지정해 주면 됩니다.(위 예제에서 Data의 크기를 배열값으로 따지면 6이 됩니다.)

lfind()함수의 다섯번째 인수는 실제 Data를 비교할 함수를 전달해야 합니다. 그런데 Program에서 문자열을 비교할때 바로 strcmp()함수를 불러들이면 좋겠지만 lfind()함수가 전달하는 Pointer형이 void형 이므로 문자열(char형)을 받는 strcmp()함수를 바로 호출하기에는 뭔가 부족합니다.

따라서 void형 Pointer를 char Pointer로 변환하여 비교해야 하므로 별도의 _strcmp()함수를 정의하고 그 안에 strcmp()함수의 호출을 통해 문자열 비교를 수행하도록 처리하는 것입니다. (여기서 strcmp()함수는 문자열 비교 후 같으면 0을 다르면 1을 반환하며 이때 비교할 두 문자열의 Pointer중 하나는 찾을 Data("fghij")이고 다른 하나는 배열의 Data("abcde"나 "fghij" 또는 "klmno"가 될것입니다.)가 됩니다.)

lfind()함수는 주어진 Data를 찾으면 그에 대한 Pointer를 반환하고 찾지 못하면 null을 반환합니다. 이를 이용해 Program의 마지막에 lfind()함수로 부터 해당 Pointer를 전달받은 값과 현재 배열크기값을 출력하도록 합니다.


다음은 lfind()함수를 사용하여 문자열대신 정수값을 선형검색을 통해 찾도록 하는 예제입니다.

#include <stdio.h>
#include <search.h>
#include <string.h>

int _intcmp(const void *a, const void *b);

main()
{
  int i[3] = {10, 20, 30};
  int *p;
  int data = 20;
  int datanum = 3;
 
  p = (int *)lfind(&data, i, &datanum, sizeof(int), _intcmp);
 
  printf("%d\n", *p);
  printf("%d\n", datanum);
}

int _intcmp(const void *a, const void *b)
{
  int i;
  int j;
 
  i = *(int *)a;
  j = *(int *)b;
 
  if (i == j)
    return 0;
  else
    return 1;
}



C의 선형탐색함수는 lfind()함수와 함께 lsearch()라는 함수도 쓰이고 있습니다. lfind()함수나 lsearch()함수는 사용하는 방법이 일치하지만 동작하는 부분에서 약간의 차이가 있습니다.

이미 언급하였지만 lfind()함수는 특정 Data를 검색 후 만일 일치하는 결과가 없으면 null을 반환하는데 비해 lsearch()함수는 일치하는 Data를 찾지 못하면 검색대상배열에 찾고자 하는 Data를 추가하고 추가된 Data의 Pointer를 반환합니다.

#include <stdio.h>
#include <search.h>
#include <string.h>

int _strcmp(const void *a, const void *b);

main()
{
  char s[4][6] = {"abcde", "fghij", "klmno"};
  char ss[6] = "pqrst";
  char *p;
  int datanum = 3;
 
  p = (char *)lfind(ss, s, &datanum, 6, _strcmp);
 
  printf("%s\n", p);
  printf("%d\n", datanum);
 
  p = (char *)lsearch(ss, s, &datanum, 6, _strcmp);
 
  printf("%s\n", p);
  printf("%d\n", datanum);
  printf("%s\n", s[3]);
}

int _strcmp(const void *a, const void *b)
{
  return strcmp((char *)a, (char *)b);
}


lsearch()함수는 Data를 찾지 못하면 배열에 찾고자 하는 해당 Data를 추가시키고 추가시킨 Data의 Pointer를 반환합니다.(lsearch()함수는 배열에 Data를 추가할때 임의로 배열의 크기를 늘리지 않으므로 배열을 선언할때 이 부분을 감안해야 합니다. (s[4][6]))


결과적으로 lsearch()함수에서는 "pqrst"와 같은 Data가 배열에 존재하지 않기 때문에 배열에 해당 Data를 추가하였으며 이에따라 배열의 크기도 4가 되었으므로 배열의 크기값을 갖는 datanum변수의 값도 1이 증가하게 됩니다.

2. 이진탐색

선형탐색은 원하는 Data를 찾기위해 처음부터 끝까지 모든 요소를 하나하나 비교해 가면서 검색을 수행합니다. 이 탐색방법은 찾아야할 Data의 요소가 1부터 100까지 100개가 있을때 100이라는 값을 찾아야할 경우 100번째까지 비교해야 하는 단점이 있습니다.

이러한 단점을 어느정도 해결한 것이 바로 이진탐색입니다.

이진탐색은 찾고자 하는 Data배열을 반으로 나누어 찾는 특징이 있는데 예를 들어 1부터 100까지 Data배열이 있을때 76이라는 Data를 찾아야 한다고 가정해 보겠습니다. 선형검색이라면 정확히 76번째까지 비교해가야 찾을 수 있겠지만 이진탐색은 우선 1에서 100까지의 배열을 1~50까지와 51~100까지 절반으로 나누어 봅니다.

그런 후 갈라진 두 Data배열을 찾을 값과 비교하게 되는데 1~50까지 나누어진 부분은 76보다 적은 수 이므로 비교해볼 필요가 없을 것이고 따라서 이 Data배열은 버리게 됩니다. 대신 남은 51~100까지의 배열을 51~75까지 그리고 76~100까지 다시 두개의 배열로 나누게 됩니다.

이렇게 하면 51~75까지는 76에 포함되지 않으므로 버리고 나머지 부분을 검색해 보면 정확히 76과 같은 Data를 찾게 되는 것입니다. 이는 결국 선형탐색보다 훨씬 적은 비교를 통해 Data를 찾을 수 있는 것으로 비교 수가 적으니 당연히 더 빠른속도로 Data를 찾을 수 있게 되는 것입니다.

C에서 이진탐색에 사용되는 함수는 baserch()함수이며 이 함수는 lsearch()함수나 lfind()함수 사용법과 거의 동일합니다. 다만 위 검색방법과 함께 baserch()함수가 stdlib.h Header File에 정의되어 있으므로 search.h대신 stdlib.h Header File을 선언해야 합니다. (bsearch()함수는 원하는 Data를 찾지 못했을 때 Null을 반환합니다.)

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

int _strcmp(const void *a, const void *b);

main()
{
  char s[4][6] = {"abcde", "fghij", "klmno", "pqrst"};
  char ss[6] = "fghij";
  char *p;
  int datanum = 4;
 
  p = (char *)bsearch(ss, s, datanum, 6, _strcmp);
 
  printf("%s\n", p);
  printf("%d\n", datanum);
}

int _strcmp(const void *a, const void *b)
{
  return strcmp((char *)a, (char *)b);
}


bsearch()함수로 "fghij"를 찾도록 합니다.(lsearch()나 lfind()함수에서는 배열 크기에 해당하는 3번째 인수부분에서 해당 변수의 주소값을 건네줬지만 bsearch()함수는 정수값 그대로 전달해야 합니다.)


주의 :
이진탐색은 Data배열을 절반으로 나누어 크기에 따라 비교하게 되므로 반드시 Data가 정렬되어 있어야 합니다.

3. 정렬

이진 탐색은 선형탐색보다 검색효율이 좋기는 하지만 검색대상이 되는 Data배열은 반드시 정렬되어 있어야 합니다.

이때 Data의 정렬방법으로는 선택정렬, 삽입정렬, quick정렬등 여러가지 정렬방법이 있는데 이중 quick정렬은 C언에서 함수를 통해 표준적으로 구현할 수 있는 정렬방법에 해당합니다.

quick정렬이 정렬하는 방식을 설명해 드리자면

예를 들어 6, 4, 2, 3, 8, 5, 7 라는 7개의 data가 있을때 이중 첫번째 값(6)을 기준(pivot)으로 정합니다. 이 기준값을 오른쪽값과 비교했을때 기준값이 더 작으면 오른쪽에 있는 값을 기준값의 왼쪽으로 밀어 버리게 됩니다. 이렇게 정렬하게 되면 결과는 다음과 같습니다.

4, 2, 3, 5, 6, 8, 7 

한번 정렬하고 난뒤 이 기준값을 기준으로 왼쪽(4, 2, 3, 5)과 오른쪽(8, 7)에 있는 Data를 나누어 처음에 정렬했던 방법과 똑같은 방법으로 다시 정렬합니다. (이때 기준값은 정렬대상에서 제외됩니다.)

4, 2, 3, 5에서는 4가 기준이 되어 정렬을 시도하게 되고 7, 8에서는 7이 기준이 되어 정렬된다고 했을때 결과는 다음과 같이 됩니다.

2, 3, 4, 5, 6, 7, 8

이 예제에서는 quick정렬을 두번 수행하여 완료하였지만 좀 더 길고 복잡한 배열인 경우 정렬수행수는 더 커질 수 있습니다. 또한 한번 정렬이 수행될때마다 해당 기준(pivot)을 기준으로 각 배열을 몇번이고 나누어 정렬을 수행하게 된다는 특징이 있습니다.

어찌보면 복잡하다는 느낌을 가질 수 도 있으나 quick정렬은 다른 정렬방식에 비해 가장 빠른성능을 내는 정렬 algorithm에 해당합니다.

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

int _strcmp(const void *a, const void *b);

main()
{
  char s[5][6] = {"klmno", "pqrst", "fghij", "abcde", "uvwxy"};
  int i;
 
  printf("정렬전\n");
 
  for (i=0; i<5; i++)
    printf("%s\n", s[i]);
 
  qsort(s, 5, 6, _strcmp);
 
  printf("\n정렬후\n");
 
  for (i=0; i<5; i++)
    printf("%s\n", s[i]);
}

int _strcmp(const void *a, const void *b)
{
  return strcmp((char *)a, (char *)b);
}


0 0