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

순차 탐색이란?

처음부터 끝까지 차례대로 모든 요소를 비교하여 원하는 데이터를 찾는 탐색 알고리즘입니다.

순차 탐색은 어느 한쪽 방향으로만 탐색할 수 있는 알고리즘이므로 선형 탐색(Linear Search)라고 부르기도 합니다.

처음부터 끝까지 모든 요소를 검사하는 전략이기에 성능은 별로 좋지 않지만, 정렬되지 않은 데이터에서 원하는 항목을 찾을 수 있는 유일한 방법이며 구현이 간단해서 버그를 만들 가능성이 적습니다.

따라서 극적으로 높은 성능을 필요로 하지 않거나 데이터의 크기가 작은 상황에서 유용하게 활용됩니다.

간단한 코드 구현

Node* SLL_SequentialSearh(Node* Head, int Target){
    Node* Current = Head;
    Node* Match = NULL;
    
    while(Current != NULL){
        if (Current->Data == Target){
            Match = Current;
        }
        else{
            Current = Current->NextNode;
        }
    }
    return Match;
}

다음 코드와 같이 말 그대로 리스트의 '처음부터 시작하여 찾는 값이 나올 때 까지' 순차적으로 찾아주면 됩니다.

한 단계 나아가 순차 탐색의 성능을 올려줄 방법을 알아보겠습니다.

바로 자기 구성 순차 탐색(Self Organizing Sequential Search)입니다. 이를 한마디로 설명하자면

자주 사용되는 항목을 데이터 앞쪽에 배치함으로써 순차 탐색의 효율을 끌어올리는 방법입니다.

대표적인 방법 3가지를 정리하겠습니다.

 

전진 이동법 

탐색된 항목을 데이터의 가장 앞으로 옮기는 방법입니다. MS 워드의 최근 문서 목록 기능과 같은 원리로 동작합니다. 따라서

한 번 탐색한 항목이 다음에 또 다시 검색될 가능성이 높은 데이터에 한해 사용해야 합니다.

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;
            if(Previous != NULL){
                Previous->NextNode = Current->NextNode;
                Current->NextNode = (*Head);
                (*Head) = Current;
            }
            break;
        }
        else{
            Previous = Current;
            Current = Current->NextNode;
        }
    }
    return Match;
}

전위법

탐색된 항목을 바로 이전 항목과 교환하는 방법입니다. 기본적으로는 전진 이동법과 비슷하지만, 전위법은 데이터의 가장 앞으로 가는것이 아니라 해당 탐색 노드의 바로 앞 노드와 교환하는 것에 차이점이 있습니다. 즉

자주 탐색된 항목을 조금씩 앞으로 옮기는 것입니다. 따라서 자주 탐색되는 항목들이 데이터 앞쪽으로 모이게 되고 이로 인해 자주 탐색되는 항목들을 빠르게 찾을 수 있게 됩니다.

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;
}

계수법

데이터 내 각 요소가 탐색된 횟수를 별도의 공간에 저장해두고, 탐색된 횟수가 높은 순으로 데이터를 재구성하는 방법입니다.

전위법을 사용하면 처음부터 데이터 앞에 위치하던 요소는 계속해서 선두를 유지할 가능성이 높고, 뒤쪽에 위치하던 요소는 많은 선택을 받더라도 데이터의 요소 개수가 많으면 앞으로 갈 수 없게 됩니다.

하지만 계수법을 사용하면 이는 데이터 순서 구성에 영향을 미치지 않게되고 오로지 탐색된 횟수만이 순서 구성에 오롯이 영향을 주는것입니다.

하지만 계수 결과를 저장하는 별도의 공간을 유지해야 하는 비용이 추가적으로 소요되겠네요.

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->Count < Current->Count){
                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;
}