[+] 검색 ① 검색 알고리즘

앞으로 다룰 검색 알고리즘에서는 동적할당을 사용한다.

선형 검색

요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는데,

이를 선형 검색이라고 한다.

 

배열의 검색 종료 조건은 아래와 같다.

 

① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우.

② 검색할 값과 같은 요소를 발견한 경우.

[ 선형 검색 알고리즘 ]

예제는 아래의 [더보기] 란을 확인한다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//선형검색
int search(int *arr,int n,int key){//key를 선형검색하는 함수
    /**
    arr: 값이 저장된 배열
    n: 반복횟수
    key: 찾고자하는 값
     */
    for(int i=0;i<n;i++){
        if(i == n-1) return -1;
        if(arr[i] == key) return i;
    }
    return 0;
}

int main(){
    int num,key;
    printf("[선형 검색]\n");
    printf("검색 개수: ");scanf("%d",&num);
    
    int *arr = (int*)malloc(sizeof(int)*num);

    for(int i=0;i<num;i++){printf("X[%d]: ",i);scanf("%d",&arr[i]);}
    printf("검색값: ");scanf("%d",&key);

    int idx = search(arr,num,key);
    switch(idx){
        case -1:
            puts("검색에 실패했습니다.");
        break;
        default:
            printf("%d(은)는 x[%d]에 있습니다.",key,idx);
            free(arr);
        break;
    }
    return 0;
}

[ 선형 검색 알고리즘: 보초법 ]

선형 검색은 반복할 때마다 위에서 언급한 종료 조건 2개를 확인한다.

하지만 종료 조건을 계산하는 비용을 줄이기 위해 이 비용을 반으로 줄이는 보초법을 사용한다.

 

이때 보초란 검색하기 전에 검색하고자 하는 값을 맨 끝 요소에 저장한 값을 말한다. 이러한 방식으로 보초를 맨 마지막 요소에 저장한 경우,  ①번 종료 조건이 필요 없어지므로 종료 판단 횟수가 반으로 줄게 된다.

 

int search(int *arr,int n,int key) /*생략*/         if(arr[i] == key) return i; /*보초법을 이용함에 따라 조건문이 두 개에서 하나로 줄어들음.*/ int main(){   int *arr = (int*)malloc(sizeof(int)*(num+1));//보초를 위한 공간 추가 할당 /*생략*/   if(idx == num) puts("검색에 실패했습니다.");       else {           printf("%d(은)는 x[%d]에 있습니다.",key,idx);           free(arr);     } }

 

보초법에서는 변수 i가 n이면 보초값이므로 검색 실패를 뜻한다.

예제는 아래의 [더보기] 란을 확인한다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//선형검색: 보초법의 사용
int search(int *arr,int n,int key){//key를 선형검색하는 함수
    /**
    arr: 값이 저장된 배열
    n: 반복횟수
    key: 찾고자하는 값
     */
    arr[n] = key;
    for(int i=0;i<n;i++)
        if(arr[i] == key) return i;
    /*보초법을 이용함에 따라 조건문이 두 개에서 하나로 줄어들음.*/
    return 0;
}

int main(){
    int num,key;
    printf("[선형 검색]\n");
    printf("검색 개수: ");scanf("%d",&num);
    
    int *arr = (int*)malloc(sizeof(int)*(num+1));//보초를 위한 공간 추가 할당

    for(int i=0;i<num;i++){printf("X[%d]: ",i);scanf("%d",&arr[i]);}
    printf("검색값: ");scanf("%d",&key);

    int idx = search(arr,num,key);
    if(idx == num) puts("검색에 실패했습니다.");
    else {
        printf("%d(은)는 x[%d]에 있습니다.",key,idx);
        free(arr);
    }
}

이진 검색

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

(단, 데이터가 키 값으로 이미 정렬돼 있다는 조건을 가진다.)

 

이진 검색을 한 단계 진행할 때마다 검색 범위가 (거의) 반으로 좁혀짐에 따라 불필요한 비교를 줄일 수 있다. 이진 검색에서 반복문은 do-while 문을 사용하는 것이 더 용이하다.

[ 이진 검색의 초기화 ]

▶ LOW : 검색 범위의 맨 앞 인덱스

▶ MID : 검색 범위의 중앙 인덱스

▶ HIGH : 검색 범위의 맨 끝 인덱스

[ 이진 검색의 종료 조건 ]

이진 검색의 종료 조건은 아래 1,2 조건 중 하나만 성립해도 된다.

 

① 중앙인덱스의 값과 KEY가 같은 경우

② 검색 범위가 더 이상 존재하지 않는 경우

[ 이진 검색의 기본 알고리즘]

int bin_search(int *arr,int n,int key){
    int LOW,MID,HIGH;
    LOW = 0,HIGH = n-1;
    do{
        MID = (HIGH+LOW)/2;
        if(key == arr[MID])return MID;
        else if(key < arr[MID]) HIGH = MID-1; 
        else  LOW = MID+1; 
    }while(LOW < MID || MID < HIGH);
    return -1;
}

알고리즘의 코드는 아래의 [더보기] 란을 확인한다.

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

int bin_search(int arr[],int n,int key){
    int LOW,MID,HIGH;

    LOW = 0;
    HIGH = n -1;
    do{
        MID = (LOW + HIGH)/2;
        if(arr[MID] == key) return MID;
        else if(arr[MID] < key) LOW = MID + 1;
        else HIGH = (MID -1);
        /**
        중앙값보다 검색하고자 하는 값이 큰 경우
        -> (중앙값+1)를 LOW로
        
        중앙값보다 검색하고자 하는 값이 작은 경우
        -> (중앙값-1)를 HIGH
         */
    }while(LOW <= HIGH);
    return -1;
    /**
    LOW  : 검색 범위 맨 앞의 인덱스 == pl
    MID  : 검색 범위 가운데 인덱스  == pr
    HIGH : 검색 범위 맨 뒤의 인덱스 == pc
    */

}

int main(){
    int num,key,cnt=0;
    printf("이진검색\n");
    printf("요소 개수: ");scanf("%d",&num);

    int *arr = (int*)malloc(sizeof(int)*num);
    printf("오름차순으로 입력하세요.\n");

    while(num > cnt){
        if(cnt == 0){
            printf("x[%d]: ",cnt);
            scanf("%d",&arr[cnt]);    
            cnt ++;
        }
        else{
            printf("x[%d]: ",cnt);
            scanf("%d",&arr[cnt]);    
            if(arr[cnt-1] < arr[cnt]) cnt ++;
            else printf("오름차순으로 다시 입력하세요.\n");
        }
    }
    printf("검색값: ");scanf("%d",&key);

    int idx  = bin_search(arr,num,key);
    if(idx == -1) puts("검색에 실패했습니다.");
    else printf("%d는 x[%d]에 있습니다.",key,idx);

    free(arr);

}

복잡도

복잡도란 프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라지는데,  이러한 알고리즘의 성능을 객관적으로 평가하는 기준을 말한다. 복잡도는 두 가지로 나뉜다.

 

· 시간 복잡도: 실행에 필요한 시간을 평가한 것

· 공간 복잡도: 기억 영역과 파일 공간이 얼마나 필요한 가를 평가한 것

 

복잡도 메트릭을 통해 시스템의 복잡도를 측정한 결과 복잡도가 높은 경우, 일반적으로 많은 장애가 유발될 가능성이 크다.

 복잡도의 형태

O(1)과 같은 상수(constant) 형태
O(log n)과 같은 로그 형태
O(n)과 같은 선형
O(n log n)과 같은 선형로그 형태
O(n^c), O(n^3)과 같은 다차 형태
O(c^n), O(3^n)과 같은 지수 형태
O(n!)과 같은 팩토리얼 형태

 

연산의 횟수가 다항식으로 표현될 경우, 계산의 편의성을 위해 불필요한 정보는 모두 버린 후 시간 복잡도를 계산한다. 

 

n/2번 실행했을 때의 복잡도는 O(n/2)가 아닌 O(n)으로서, n의 값이 무한히 커진다고 해도 복잡도는 O(n)으로 표시한다. 이는 컴퓨터의 계산 속도가 인간이 느낄 수 있는 범위를 넘어가기 때문이다.

괄호 안의 수는 정확한 값이 아닌 비례의 관계로 이해는 것이 좋다.

 

n이 점점 커짐에 따라 O(n)에 필요한 계산 시간은 n에 비례하여 커지지만 O(1)에 필요한 계산시간은 변하지 않는다.

 

일반적으로 O(f(n))과 O(g(n))의 복잡도의 계산은 다음과 같다.

 

O(f(n)) + O(g(n)) = O(max(O(f(n)),O(g(n)))

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 더 우선 시 한다.

다시 말해, 복잡도는 차원이 가장 높은 복잡도를 선택한다.

bsearch 함수를 이용한 이진 검색

아래 링크의 필자의 포스팅을 참조한다.

[집합과 검색] #4. bsearch 함수를 이용한 이진검색

함수 포인터

함수 포인터는 이름 그대로 함수를 가리키는 포인터이다. 함수 포인터의 자료형은 가리키는 함수에 따라 다르다.

이때 괄호에 항상 유의한다.

double func(int)       //int를 받아드려 double를 반환

double (*pf)(int)      //int를 받아드려 double을 반환하는 함수에 대한 포인터

double *pf(int)        //int를 받아드려 double에 대한 포인터를 반환하는 함수

 

괄호를 생략하면 포인터가 아니라 포인터를 반환하는 함수(함수는 반환값의 자료형을 따르기 때문)로 선언된다.