0x03.탐색 알고리즘:선형 탐색

탐색 알고리즘

레코드(record)는 임의의 객체에 대한 정보를 나타내는 다수의 필드(field)로 구성되어 있는데, 여러 개의 레코드를 명확하게 구별할 때 사용되는 키(key) 필드도 이에 포함된다.

(레코드의 구조체로는 파일(file)과 테이블(table)이 있다.)

탐색이란 어떤 키 K를 가진 레코드가 파일 상에 있는지 조사하는 절차로, 탐색을 요청할 경우에 기입하게 되는 것이 키이고, 탐색 후의 출력 결과가 레코드의 위치가 된다. 컴파일러의 경우 식별자 이름이 키가 되고, 식별자에 붙어있는 여러가지의 정보를 포함한 것이 레코드가 된다.

탐색을 하기 위해서는 키에 대한 조건을 지정해야 하는데, 다음과 같이 세부적으로 나눌 수 있다.

(파일상에 존재하는 모든 레코드가 갖는 키가 각자 다르다는 전제가 필요)

① 일치형 조건

      하나 이상의 키에 대해 값을 직접 지정하고, 지정된 값과 일치하는 것을 찾는 방식(직관적)

② 구간형 조건

      키가 취할 수 있는 값을 범위로 지정하여 찾는 방식(추측)

③ 접근형 조건

      지정한 값에 가까운 레코드를 찾는 방식

④ 조건 지정형

      여러 키 사이에 성립하는 조건을 논리식으로 지정하는 방식

탐색 알고리즘을 개발할 경우에 고려해야 할 점은 탐색조건과 탐색하는 속도뿐만이 아니다. 새로운 데이터를 파일에 등록하거나 삽입하는 속도, 데이터를 삭제하는 속도 등을 추가적으로 고려해야 한다. 정적 파일(static file)의 경우에는 새로운 데이터를 삽입하는 경우가 없으므로 탐색 속도만 고려하여도 충분하지만, 동적 파일(dynamic file)의 경우에는 삽입과 삭제 과정이 자주 발생하기 때문이다. 이와 같은 이유로 알고리즘의 선택은 어떤 종류의 파일을 사용하는가에 따라 다르게 고려되여야 한다.

1. 선형 탐색(linear search)

가장 단순한 알고리즘으로 순차탐색이라고도 한다. 이 방식은 데이터가 저장되어 있는 배열이나 리스트를 처음부터 순차적으로 비교하면서 찾는 방식이다.

위 그림의 예로, 데이터 4를 찾기 위해서 첫 배열요소 값인 3부터 시작하여 8, 22, 50, 4순으로 순차적으로 탐색을 실시한다. 만약 배열 상에 해당 데이터가 존재하지 않으면 탐색이 실패한다. 파일을 쉽게 구성하는 방법은 배열을 만들고 앞에서부터 차곡차곡 데이터를 저장하는 방식인데, 이 경우, 레코드를 넣을 데이터의 개수와 변수만 있으면 된다.

#define true 1

#define false 0

#define SIZE 10

typedef int index;

typedef int keytype;

typedef int boolean;

typedef char othertype;

struct array{

     keytype key;

     othertype otherinfo;

};

struct array arry[SIZE];

아래는 탐색에 활용되는 알고리즘이다.

void search(keytype target, boolean *found, index *pos){

     *found=false;

     *pos=1;

     while(pos<=n&&target!=arry[pos].key) *pos=*pos+1;

     *found=(*pos<=n) ? true : false;

target을 탐색 시도하여 발견하면 found를 true로, 발견하지 못하면 false로 지정한다. pos에는 찾고자 하는 데이터 배열의 위치가 값으로 들어간다.

아래는 삽입 알고리즘이다.

void insert(keytype x, othertype y){

     if(n>=SIZE-1) exit(1);

     n=n+1;

     arry[n].key=x;

     arry[n].otherinfo=y;

배열의 크기를 비교하고 배열의 마지막에 데이터를 삽입한다.

(2번째 줄을 보면 배열의 한 칸을 남기는데, 이는 좀있다 설명할 보초값을 사용하기 위해 남겨둔다.)

아래는 pos번째(찾고자 하는 데이터의 배열 위치)의 레코드를 삭제하는 알고리즘이다.

void delete(index pos){

     index i;

     for(i=pos;i<n-1;i++){ arry[i]=arry[i+1] ;};

     n=n-1;

}

위 코드를 통해, 삭제할 pos번째 레코드의 뒷부분에 위치한 배열의 값들을 한 칸씩 앞으로 이동시켰다.

● 보초기법을 사용한 변형된 탐색 알고리즘

void search(keytype target, boolean *found, index *pos){

     arry[n+1]=target;

     *pos=1;

     while(target!=target[pos].key){ *pos=*pos+1; };

     *found=(*pos<=n) ? true : false;

}

아까 본 알고리즘과 살짝 다른데, 위의 알고리즘을 사용하면 탐색을 하기 전에 배열의 마지막에 탐색하려는 키 값을 미리 넣게되는데, 이를 아까 언급한 보초값(sentinel value)라고 한다. 이렇게 배열의 마지막에 값을 추가함으로써, 탐색할 레코드가 존재하지 않을 경우라도 배열의 마지막에서는 찾고자 하는 데이터를 찾을 수 있기 때문에, 그 전 알고리즘과 같이 반복적으로 pos값이 n을 넘는지를 조사할 필요가 없다. 이로 인해 반복할 때마다, 한 루틴이 기존에 비해 줄어드는 효과가 있다. 이 기법을 보초기법이라고 하며, 이 경우에는 SIZE-1개까지의 데이터를 사용할 수 있다.