[알고리즘] 순차 탐색

 

자료들이 뒤섞이고 잘 정리되어 있지 않다면 원하는 자료를 빨리 찾기 쉽지 않을 것이다.

만약 자료들이 일정한 규칙에 따라 잘 정리되어 있으면 훨씬 효율적인 탐색이 가능할 것이다.

결국 탐색 알고리즘은 자료들이 어떻게 정리되어 있는가에 많은 영향을 받는다.

 

이진 탐색 방법에 대해 알아보자!

 

 

# 탐색이란?

사람들은 항상 무언가를 찾아 헤맨다.

입고 나갈 옷을 찾거나 점심 식사를 위해 맛집을 찾고, 여행에서 찍은 사진을 검색한다.

이것은 컴퓨터에서도 마찬가지이다.

탐색은 컴퓨터에서 가장 흔한 작업의 하나이고. 많은 시간이 요구되기 때문에 효율적인 탐색은 매우 중요하다.

 

탐색은 데이터의 집합에서 원하는 조건을 만족하는 데이터를 찾는 작업이다.

탐색을 위한 대상을 보통 레코드(record)라 하고, 이러한 레코드의 집합을 테이블(table)이라고 부른다.

하나의 레코드는 여러 개의 필드로 이루어지는데, 이 중에서 탐색의 기준이 되는 필드 키(key) 또는 탐색키(search key)라고 부른다.

결국 탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업이다.

 

탐색에서는 테이블을 구성하는 방법에 따라 효율이 달라진다.

가장 간단한 방법은 배열을 사용해 레코드를 저장하고 찾는 것이다.

만약 성능을 더 높이고 싶다면 이진 탐색 트리나 해싱 같은 더 진보된 방법을 사용해야 한다.

탐색 방법을 선택할 때는 당연히 탐색 연산의 효율이 가장 중요하겠지만,

테이블에 레코드를 추가하거나 꺼내는 삽입과 삭제 연산도 마찬가지로 중요하게 고려해야 한다.

만약 테이블이 한번 만들어지면 수정할 필요가 없이 탐색 작업만 반복되는 응용이라면 탐색 연산의 효율만 생각하면 된다.

그러나 레코드의 삽입과 삭제가 빈번하게 일어나는 응용이라면,

탐색과 함께 삽입과 삭제 연산의 비용을 종합적으로 고려해 알고리즘을 선택해야 한다.

 

 

# 순차 탐색

순차 탐색(sequential search) 또는 선형 탐색(linear search)은

일렬로 늘어선 자료(레코드)중에서 원하는 킷값을 가진 레코드를 찾는 알고리즘이다. 

테이블은 배열이나 연결 리스트로 구성될 수 있다.

 

순차 탐색은 테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 찾는다.

순서대로 모든 레코드를 검사하므로 레코드들이 뒤죽박죽 무질서하게 섞여 있어도 항상 원하는 레코드를 찾을 수 있다.

 

위 그림을 통해 처리 과정을 알아보자.

탐색을 위한 레코드는 리스트에 저장되어 있고, 탐색의 범위는 low에서 high까지라고 가정하자.

순차 탐색은 리스트의 low 위치에서 순서대로 레코드를 탐색키와 비교하는데, 만약 같으면 그 레코드의 위치를 반환한다.

만약 high 까지도 원하는 레코드가 나타나지 않으면 탐색 실패이므로 -1(유효한 범위 밖임을 의미)을 반환한다.

예를 들어, 킷값이 56인 경우는 네 번만에 탐색에 성공하고, 찾은 위치 low+3을 반환한다.

만약 62를 탐색한다면 high 까지도 원하는 레코드가 없으므로 탐색은 실패하고 -1을 반환한다.

이러한 순차 탐색 알고리즘은 다음과 같다.

function sequential_search(A, key, low, high) {
	for (let i= low; i < high+1; i++) {	// i : low, low+1.  ... , high
    	if(A[i] == key) { // 탐색 성공하면
        	return i; // 인덱스 반환
        }
    return -1; // 탐색 실패하면 -1 반환
    }
}

 

 

 

# 순차 탐색은 얼마나 빠를까?

순차 탐색에서 가장 운이 좋은 경우는 찾는 자료가 맨 앞에 있는 경우이다.

이 경우 1번의 비교만으로 탐색이 완료된다.

그러나 최악의 겨우는 찾는 레코드가 테이블의 맨 뒤에 있거나 리스트에 없는 키를 찾는 경우이다.

이 경우 항상 모든 레코드를 탐색해야 하므로 탐색 범위만큼 비교가 필요하다.

즉, 테이블의 크기가 n이라면 시간 복잡도는 O(n)이 된다.

 

 

 

# 순차 탐색의 특징

1. 탐색의 정의를 직접 사용하는 알고리즘으로 간단하고 구현하기 쉽다.

2. 효율적이지 않다. 탐색 성능은 최선의 경우 O(1)이고 최악이나 평균적인 경우가 O(n)인데, 최선의 경우는 큰 의미가 없다.

3. 테이블이 정렬되어 있지 않다면 순차 탐색 이외에 별다른 대안은 없다.

 

 

# 순차 탐색을 개선 하는 방법은?

순차 탐색을 개선하는 방법이 있을까? 모든 경우에 적용할 수 있는 묘책은 없지만 불가능 한 것은 아니다.

전략1은 다음과 같다.

레코드 중에서 자주 검색되는 것들을 가능한 한 앞에 두는 것이다.

앞에 있는 레코드는 더 빨리 찾을 수 있기 때문이다.

이것은 마트에서 행사 제품을 매장 입구에 진열하는 것과 같은데, 사람들이 많이 찾는 인기 상품을 더 쉽게 찾을 수 있도록 하려는 것이다.

이러한 방법은 자기 구성(self-organizing) 순차 탐색이라고 한다.

탐색이 진행될때마다 자주 사용되는 레코드를 앞쪽으로 옮기는 방법으로 리스트를 재구성하여 탐색의 효율을 끌어올리려는 것이다.

이런 리스트를 자기 구성 리스트라고 하는데 리스트를 재구성 하는 방법을 알아보자.

 

 

 

# 자기 구성 리스트 생성 방법

1. 맨 앞으로 보내기(move to front)

가장 간단한 방법은 탐색에 성공한 레코드를 리스트의 맨 앞으로 보내는 방법이다.

아래 그림에서 28의 탐색이 성공하면 이 레코드를 리스트이 맨 앞으로 옮긴다.

배열 구조의 리스트에 이 방법을 적용하는 경우 28 이전의 모든 레코드를 한 칸씩 뒤로 밀어야 한다.

 

연결된 구조는 28과 바로 앞 노드인 56의 링크만 수정한 다음 시작 노드를 28 노드로 연결하면 된다.

연결된 구조가 복잡하지만 훨씬 효율적으로 처리할 수 있다.

물론 이 방법이 모든 상황에 적합한 것은 아니고,

한번 탐색된 레코드가 바로 이어서 다시 탐색될 가능성이 많은 응용에만 사용해야 한다.

 

 

 

2. 교환하기(transpose)

탐색된 레코드를 맨 앞이 아니라 바로 앞의 레코드와 교환할 수도 있다.

예를 들어, 아래 그림에서 28이 탐색되면 위치를 바로 앞의 레코드인 56과 교환한다.

자주 탐색되는 레코드는 점진적으로 앞으로 이동하고, 그렇지 않은 레코드는 점진적으로 뒤로 밀리는 효과가 있다.

 

이 전략을 기존의 순차 탐색 에 적용하면 다음과 같다.

// 교환하기 전략이 추가된 순차 탐색 알고리즘

function sequential_search_transpose(A, key, low, high) {
	let temp; // 값 교환시 사용될 변수
	for (let i= low; i < high+1; i++) {	// i : low, low+1.  ... , high
    	if(A[i] == key) { /
        	if(i > low) { // 맨 처음 요소가 아니면
            		temp = A[i]; // 교환하기(transpose)
                	A[i] = A[i-1]; // 한 칸 앞으로 온다
               		A[i-1] = temp;
            }
         	return i // 탐색에 성공하면 키 값의 인덱스 반환
        }
    }
    return -1; // 탐색 실패하면 -1 반환
}

 

이 외에도 레코드마다 탐색된 횟수를 별도의 공간에 각각 저장해두고,

탐색된 횟수가 많은 순으로 테이블을 재구성하는 전략(frequency count method)을 사용할 수 있다.

이러한 방법들도 모두 '지금까지 더 많이 탐색된 레코드가 앞으로도 더 많이 탐색될 가능성이 큰' 응용에만 적용되어야 한다.