탐색 알고리즘 - 순차 탐색(Sequential Search)

순차 탐색은 데이터의 집합(링크드 리스트, 배열등)을 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 알고리즘입니다.

 

순차 탐색은 '처음부터 끝까지 순서대로'라는 전략 때문에 효율은 나쁘지만, 구현이 간단하고 버그를 만들 가능성이 적어 높은 성능이 필요하지 않은 곳에서는 유용하게 사용됩니다.

 

아래의 코드는 링크드 리스트와 배열의 순차 탐색 코드 예입니다.

ode* SLL_SequentailSearchNode(Node* Head, int Target) { //링크드 리스트를 위한 순차탐색
    Node* Current = Head; 
    Node* Match = NULL; // 탐색할 타겟과 일차하는 노드
 
    while (Current != NULL) { //노드가 널이 아닐동안 => 널이면 빠져나옴
        if (Current->data == Target) { // 노드의 데이터와 타겟이 일치하면
            Match = Current; // 매치노드에 노드대입
            break; // 반복문 빠져나옴
        }
        else {
            Current = Current->NextNode; // 아니면 다음노드 이동
        }
    }
    return Match;
}
 
int Arr_SequentailSearch(int DataSet[], int Target, int size) { // 배열을 위한 순차탐색
 
    int Target_index = 0; // 타겟 인덱스 번호
 
    for (int i = 0; i < size; i++){ // 배열의 크기만큼 반복
        if (DataSet[i] == Target) { // 배열의 데이터와 타겟 일치하면
            Target_index = i;
            break;
        }
    }
    return Target_index;
}

효율이 나쁜 순차 탐색을 조금이라도 더 효율적으로 사용하려면 어떻게 해야 할까요?

 

단순하게 생각해보자면, 처음부터 끝까지 데이터를 탐색할 때 찾을 데이터가 앞에 위치해있으면 데이터를 뽑아낸 후 반복문을 빠져나올 수 있습니다.

 

이와 같이 자주 사용되는 데이터를 데이터 집합의 앞쪽의 배치함으로써 순차 탐색을 효율을 끌어올리는 알고리즘을 자기 구성 순차 탐색이라고 합니다.

 

자기 구성 순차 탐색은 다음의 세 가지 방법이 있습니다.

• 전진 이동법(Move to Front)
• 전위 법(Transpose)
• 계수법(Frequency Count)

 

지금부터 이 세 가지의 방법에 대해 알아보도록 하겠습니다.

 

전진 이동법

---

전진 이동법(Move to Front)은 어떤 데이터가 탐색되고 나면, 그 데이터를 데이터 집합 제일 앞쪽의 배치시키는 방법입니다. 이렇게 하면 연이어 같은 데이터를 탐색하는 경우에 한 번에 데이터 탐색을 완료할 수 있습니다.

 

하지만 데이터 집합 내에서 특정한 항목들이 집중적으로 탐색 대상이 되는 경우는 매우 드물기 때문에 자주 사용되지는 않을 거 같죠...?

 

아래의 코드는 링크드 리스트와 배열의 전진 이동법의 예시입니다.

Node* SLL_MoveToFront(Node** Head, int Target) { //링크드리스트 전진 이동 순차 탐색
    Node* Current = (*Head);
    Node* Previous = NULL;
    Node* Match = NULL;
 
    while (Current != NULL) { // 현재 노드가 널이 아닐동안 반복
        if (Current->data == Target) { // 타겟과 데이터 일치하면
            Match == Current; // Match에 저장
            if (Previous != NULL) { // 이전노드가 널이 아니면 => 두번째 노드부터
                Previous->NextNode = Current->NextNode; // 이전노드의 다음 노드를 현재 노드의 다음 노드로 연결
 
                Current->NextNode = (*Head); // 현재 노드의 다음 노드는 헤드
                (*Head) = Current; // 헤드가 현재 노드가 됨
            }
            break;
        }
        else { // 타겟 노드와 일치하지 않으면
            Previous = Current; // 현재 노드는 이전 노드가 되고
            Current = Current->NextNode; // 현재 노드는 현재 노드의 다음 노드가 됨 => 한칸 이동
        }
    }
    return Match;
}
 
int Arr_MoveToFront(int DataSet[], int Target, int size) { // 배열 전진 이동 순차 탐색
    int Prev = 0;
    int Target_index = 0;
 
    for (int i = 0; i < size; i++) {
        if (DataSet[i] == Target) {
            Target_index = i;
            if (i != 0) {
                memmove(&DataSet[1], &DataSet[0], sizeof(DataSet[0]) * i); 
                // 첫 번째 매개변수는 이동할 새로운 주소
                // 두 번째 매개변수는 이동할 데이터가 어디서 부터인지를 나타내는 주소
                // 세 번째 매개변수는 얼마만큼 옮길건지를 표현하는 byte
                DataSet[0] = Target;
            }
            break;
        }
    }
    return Target_index;
}
}

 

전위 법

---

전위 법은 탐색된 데이터를 바로 이전 항목과 교환하는 알고리즘 입니다. 전진 이동법은 탐색된 데이터를 무조건 앞에 옮기지만, 전위법은 자주 탐색된 항목을 점진적으로 이동시킵니다. 그래서 자주 사용되는 데이터들을 상대적으로 앞쪽에 위치하게 되는 것입니다.

 

아래의 코드는 링크드 리스트와 배열을 전위 법 예시입니다.

Node* SLL_Transpose(Node** Head, int Target) {
    Node* Current = (*Head);
    Node* PPrevious = NULL; // 이전노드의 이전노드
    Node* Previous = NULL; // 이전노드
    Node* Match = NULL;
 
    while (Current != NULL) {
        if (Current->data == Target) { // 타겟과 데이터 일치하면
            Match = Current; // 매치노드에 현재노드 저장
            if (Previous != NULL) { // 이전노드 널이 아니면
                if (PPrevious != NULL) { // 이전노드의 이전노드가 널이 아니면
                    PPrevious->NextNode = Current; // 이전이전노드의 다음노드는 현재노드
                }
                else { // 이전노드의 이전노드가 널이면
                    (*Head) = Current; //헤드노드가 현재노드
                }
 
                Previous->NextNode = Current->NextNode; // 이전노드의 다음노드는 현재노드의 다음노드
 
                Current->NextNode = Previous; // 현재노드의 다음노드는 이전노드가 된다
            }
            break;
        }
        else {
            if (Previous != NULL) { // 타겟 일치하지 않으면
                PPrevious = Previous;
                Previous = Current;
                Current = Current->NextNode;
            }
        }
    }
    return Match;
}
 
int Arr_Transpose(int DataSet[], int Target, int size) {
    int Target_index;
    int temp; // 값 교환시 사용될 변수
    for (int i = 0; i < size; i++){
        if (DataSet[i] == Target) {
            Target_index = i;
            if (i != 0) {
                temp = DataSet[i - 1];
                DataSet[i - 1] = DataSet[i];
                DataSet[i] = temp;
            }
                break;
        }
    }
    return Target_index;
}

 

계수법

---

계수법(Frequency count)은 데이터 집합 내의 데이터가 탐색된 횟수를 별도의 공간에 저장해 두고, 탐색된 횟수가 높은 순으로 데이터를 재배치시키는 알고리즘입니다. 전위 법보다 데이터를 탐색하는 데 있어서는 효율적이지만, 횟수를 저장하는 별도의 공간을 둬야 하고 데이터 집합을 재배치시키는 등 알고리즘 실현을 위한 비용이 많이 소모됩니다.