탐색 알고리즘 - 다양한 탐색법

컴퓨터의 기억공간 내에 저장한 특정 항목의 위치를 찾거나 자료가 집합 내에 없을 경우에는 특정한 메시지를 출력하여 주는

운영 방법을 탐색이라고 합니다. 컴퓨터를 이용하는 최고의 목적은 정보를 저장하고 정리한 후 탐색하는 것이죠. 탐색에 들어가기전

알아야할 용어들이 있습니다.

기본적인 용어는

키 : 키는 파일 내의 레코드를 다른 레코드와 구별할 수 있는 항목

기본키 : 특별히 각 레코드를 완전히 구분할 수 있는 검색키

레코드 : 1개 이상의 항목들을 서로 관련 있는 것끼리 짝을 지어 모은 형태

딕셔너리 : 검색이라는 자료 처리를 하기 위하여 키와 레코드 및 기본 연산들을 자료 구조 형태로 표현해 놓은 것

심벌 테이블 : 프로그램에 대한 딕셔너리로 자료 구조에 대한 모든 명세들을 가지고 있으며 보통 이름과 값으 쌍으로 구성 됩니다.

순차 탐색법

가장 간단한 탐색 방법이 바로 순차 탐색 방법입니다. 이 방법은 배열이나 연결 리스트에서 사용할 수 있는 방법으로, 첫 번째 레코드

부터 차례차례로 비교해 가면서 해당 키값을 가지고 있는 레코드를 찾아내는 방법입니다. 만약 원하는 자료가 있다면 그 자료의

인덱스를 되돌려 주면 되고, 없다면 널값을 되돌려 주면 됩니다.

순차 탐색은 크게 2가지 방법론이 있습니다. 비정렬과 정렬일때 탐색과 정렬된 자료에서의 탐색입니다.

비정렬 자료에서의 순차 탐색에서 비정렬 자료란 n개의 레코드가 키값에 관계없이 순서 없이 저장된 형태입니다. 찾고자 하는 레코드

의 키값을 배열이나 연결 리스트로 표현한 파일 내의 레코드를 처음/끝에서부터 하나씩 차례로 비교하여 찾을 때까지 수행하는 방법

입니다.

정렬된 자료에서의 선형 탐색은 레코드들이 키값에 따라 오름차순/내림차순으로 미리 정렬 되어 있으므로 처음부터 순서대로 키값과

비교하면서 원하는 레코드를 쉽게 찾을 수 있는 방법입니다. 원하는 키값보다 큰 값의 키를 가진 레코드 위치에서도 레코드를 찾지 

못할 경우에는 중도에서 수행을 끝냅니다.

typedef struct record{
    int key;
}record;
record s_file[MAX];
 
typedef struct record{
    int key;
    struct record *link;
}*record;
 
int sequential_search(int n, int key)
{
    int i =0;
    while(i<=n-1)
    {
    if(s_file[i].key= =key)
        return(i);
    i+ +;
 }
    return(NULL);
}

순차 탐색에서 주의점은 배열의 크기를 미리 충분히 할당하고 배열의 상한선을 넘어서 자료가 삽입되지 않도록 해야 합니다. 이러한

문제를 해결하기 위한 방법이 자료의 크기를 동적으로 변경할 수 있는 선형 연결 리스트를 이용하는 것입니다. 자료를 연결

리스트를 이용하여 구성할 경우 자료를 삭제하려는 경우에도 매우 큰 장점을 발휘하죠. 그러나 연결 리스트에서도 효율적인 순차

탐색을 수행하기 위해서는 가장 빈번하게 탐색되는 자료를 자료 구조의 앞부분에 위치시키는 것이 좋습니다.

이진 탐색법

이진 탐색법은 반드시 정렬되어 있는 순서 파일에서만 가능한 검색 방법으로 분할 정복 개념에 기본을 둔 방법입니다. 레코드 수가 

많은 큰 파일에서 효율적으로 전체 파일을 두 부분으로 나누어 찾아야 하는 레코드 수가 많은 큰 파일에서 효율적으로 전체 파일

을 두 부분으로 나누어 찾아야 하는 레코드가 어느 부분에 있는가를 결정한 후 그부분으로 가서 원하는 레코드를 찾을 때까지 이

과정을 반복하게 되는 것이죠.

배열 표현의 이진 탐색은 정렬이 선행되어 있으면, 분할 후 정복 기법을 사용하여 탐색하는 대표적인 알고리즘 입니다.

이진 탐색 과정에는 3가지 상태가 있습니다. 아 참고로 분할 정복 방법의 사전적 의미는 "어떤 문제를 해결하는 알고리즘에서 원래 문제

를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식." 입니다. 이어서 3가지 상태는

find_key<keys[mid]인 경우 : 찾고자 하는 키는 keys[1]부터 keys[mid-1]사이에 존재

find_key=keys[mid]인 경우 : 원하는 키를 찾은경우

find_key>keys[mid]인 경우 : 찾고자 하는 키는 keys[mid+1]부터 keys[n] 사이에 존재하는 경우

이진 탐색 알고리즘은 깊이(d) = logn +1, 비교 횟수=(logn+1), 시간 복잡도= O(logn)의 특징을 갖고 있으며, 이진 탐색 알고리즘에 

적합한 기억장치는 주기억장소 탐색에 적합합니다.

이진 탐색 나무

이진 탐색 나무는 나무에 존재하는 각 노드들이 K1,K2...Kn의 키값을 갖는 n개의 레코드들 중 하나를 갖는 나무를 말합니다. 여기서 

키들은 노드의 식별자이므로 이진 나무에서 어떤 노드를 찾는다는 것은 그 노드의 키값을 찾는다는 것과 같은 의미가 되죠.

이진 탐색 나무는 임의의 노드에 대해 왼쪽 부나무에 존재하는 노드들의 키값은 그 노드의 키값보다 앞서야 하며 오른쪽 서브나무

에 있는 모든 노드들의 키값보다 앞서도록 구성해야 합니다. 즉 먼저 노드들 사이의 관계를 규정하고 다음 노드의 위치를 결정하게

되는 것입니다.

struct Node{
    string key;
    int info;
    Node left;
    Node right;
}

이진 탐색 나무를 탐색할 경우는 전위 운행, 중위 운행, 후위 운행인 순차 탐색 외에도 직접 탐색법을 사용합니다. 순차 탐색의 경우는

중위 운행 알고리즘을 구현하기 보다 편리하므로 다른 운행법에 비해 많이 사용합니다. 직접 탐색법은 이진 탐색 나무의 특징인 어떤

키값을 갖는 노드가 그 나무에 있는지 없는지를 알 수 있다는 점을 이용한 방법이죠.

이진 탐색 나무의 삽입

특정 노드를 이진 탐색 나무에 삽입하려면 같은 키값을 가지는 노드가 없어야 합니다. 동일한 키를 가지고 노드의 존재여부와 삽입할 

위치를 알아냅니다.

이진 탐색 나무의 삭제

특정 키값을 가지는 노드를 삭제하려면 먼저 검색 연산을 하여 삭제할 노드를 찾아냅니다.

이진 탐색 나무의 탐색 속도는 O(logn +1)이고 삽입/삭제 시 자료 이동 횟수는 O(logn) 입니다 이진 탐색 나무 알고리즘에 적합한 

것은 주기억장소에서의 탐색입니다. 이진 탐색 나무에서 삽입/삭제 조작 시 문제점이 있는데, 불균형인 이진 탐색 나무로 변화 시에는

탐색 속도가 늘어나는 것이 단점이죠. 

최악의 경우 경사진 이진 나무를 생성하게 되는데 이경우에는 탐색 속도가 O(n)으로 최악의 효율을 나타낼 수도 있습니다.