[ 자료구조 ] 탐색 - 01 . 순차탐색

[순차 탐색]

[순차 탐색]

순차 탐색은 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘이다 .

한쪽 방향으로만 탐색을 수행한다고 해서 선형탐색이라 불리기도 한다 .

 

효율적인 방법은 아니지만 , 정렬되어 있지 않은 데이터 집합 사이에서 원하는 데이터를 찾을 수 있는 유일한 방법이며,

구현이 간단해서 극적으로 높은 성능이 필요 없거나 데이터 집합의 크기가 작은 곳에서 사용된다 .

 

[예시]

링크드 리스트를 위한 순차 탐색 구현의 예이다.

Node* SLL_SequentialSearch(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;
}

 

[자기 구성 순차 탐색]

[ 자기 구성 순차 탐색 ]

다음의 경우의 공통점은 ?

• 슈퍼마켓에서 특별 행사 제품을 매장 입구쪽에 진열한다 .
• MS 워드의 최근 문서 목록
• 단골 중국집 전화번호 스티커를 냉장고에 붙인다 .

=>자기 구성법은 자주 찾는 항목을 다른 항목보다 우선하여 접근 할 수 있게 가까운 곳에 배치한다 .

자기구성순차탐색은 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치하여 검색효율을 끌어올린다 .

 

[ 세가지 방식 ]

"자주 사용되는 항목을 어떻게 선별하는가"에 따라 다음 세가지 방법으로 나뉜다 .

1. 전진 이동법 (Move To Front)
2. 전위법 (Transpose)
3. 빈도 계수법 (Frequency Count)

[ 전진 이동법 ]

어느 항목을 탐색후 항목을 데이터 집합의 가장 앞에 위치시킨다 .

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
        {
        	Previos = Current;
            Current = Current -> NextNode;
        }
    }
}

[ 전위법 ]

탐색된 항목을 바로 이전 항목과 교환한다 .전위법은 자주 탐색된 항목을 점진적으로 앞으로 옮긴다 .

이로 인해 자주 탐색되는 항목들은 앞쪽으로 모여 빠르게 찾을 수 있다 .

 

구현은 다음과 같다 .

Node* SLL_Transpose(Node ** Head , int Target)
{
	Node* Currenr = (*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;
}

[ 계수법 ]

데이터 집합 내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장 , 탐색된 횟수가 높은 순으로 데이터 집합을 재구성한다 .

전위법은 가장 뒤에 있는 데이터가 가장 많은 선택을 받더라도 데이터 집합의 크기가 크다면 가장 앞에 온다는 보장이 없다. 다만 계수법은 횟수를 저장할 공간과 데이터 집합의 재배치 또한 필요하기에 비용이 더 많이 소요되는 방법이다.