탐색 알고리즘 개요
여러 개의 자료 중 원하는 자료를 찾는 작업을 탐색이라고 합니다. 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업이며 또한 많은 시간이 요구되는 작업이기에 효율적으로 하는 것이 중요합니다. 탐색 알고리즘을 구현하기 위해 사용되는 자료구조는 매우 다양합니다. 그 중 배열을 사용하여 자료를 저장하고 찾는 방식이 가장 기초적이나, 탐색 성능을 높이기 위해서는 "이진 탐색 트리"와 같은 더 나은 방식을 사용하기도 합니다.
탐색 알고리즘의 기초 단위는 "항목"입니다. 이 항목은 간단한 숫자일 수도, 구조체가 될 수도 있습니다. 항목 안에는 항목과 항목을 구별하는 "키(Key)"가 존재하며 이를 "탐색 키(Search Key)"라고 합니다. 탐색은 바로 "탐색 키와 데이터로 이루어진 여러 항목 중에서 원하는 탐색 키를 가진 항목을 찾는 것"입니다.
탐색 알고리즘 종류
탐색 알고리즘은 "정렬되지 않은 리스트에서 탐색하는 방법"과 "정렬된 리스트에서 탐색하는 방법"으로 나뉩니다. 정렬되지 않은 리스트에서 탐색하는 방법으로는 "순차 탐색"이 있으며, 정렬된 리스트에서 탐색하는 방법으로는 "이진 탐색", "색인 순차 탐색", "보간 탐색"이 있습니다.
이제부터 본격적인 탐색 알고리즘들을 살펴보도록 하겠습니다.
순차 탐색 (Sequential Search)
순차 탐색 방법
순차 탐색은 정렬되지 않은 리스트의 항목들을 처음부터 마지막까지 하나씩 순차대로 검사하여 원하는 항목을 탐색하는 방법입니다. 단방향으로 진행하는 탐색 방법이기에 "선형 탐색(Linear Search)"이라고도 불립니다.
즉, 배열을 선언한 후 배열의 앞에서부터 탐색값과 일치하는 항목을 찾을 때까지 하나하나 순차적으로 탐색합니다. 탐색값과 일치하는 항목을 찾으면 그 항목의 인덱스를 반환하고, 탐색값과 일치하지 않는 경우 반복문을 빠져나와 -1을 반환합니다.
위의 방법이 바로 가장 기본적인 순차 탐색 방법입니다. 그런데 이 순차 탐색 방법을 약간 개선할 수 있습니다. 기본적인 방법은 리스트 전체를 탐색하며(for문) 리스트의 끝을 테스트하는 비교 연산이 있고 그 반복만 안에 키 값을 비교하는(if문) 연산이 있습니다. 이것은 약간 비효율적입니다.
리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 종료조건을 키 값을 찾을 때까지로 설정하면 리스트의 끝을 테스트하는 비교 연산(i <= high)의 수를 줄일 수 있습니다. 즉, 매번 리스트의 끝에 도달했는지 살필 필요가 없게 됩니다. 그렇기에 더 빠른 방식으로 순차 탐색이 가능합니다.
순차 탐색 구현 (C언어)
#include <stdio.h>
#define MAX_SIZE 10
int list[MAX_SIZE];
// 순차 탐색
int seq_search(int key, int low, int high) {
int i;
for(i = low; i <= high; i++) {
if (list[i] == key)
return i; // 탐색에 성공하면 키 값의 인덱스 반환
}
return -1; // 탐색에 실패하면 -1 반환
}
// 개선된 순차 탐색
int seq_search2(int key, int low, int high) {
int i;
list[high + 1] = key;
for(i = low; list[i] != key; i++) // 키값을 찾으면 종료
;
if (i == (high + 1)) return -1; // 탐색 실패
else return i; // 탐색 성공
}순차 탐색의 시간 복잡도 분석
순차 탐색 알고리즘은 리스트의 처음부터 탐색을 시작하여 항목을 찾거나, 모든 항목을 검색할 때까지 항목의 키 값을 비교하게 됩니다. 순차 탐색 알고리즘이 탐색에 성공할 경우, 탐색을 위한 평균 비교 횟수는 다음과 같습니다.
$$ (1 + 2 + 3 + \cdots + n) / n = (n + 1) / 2 $$
탐색에 실패할 경우에는 $n$번 비교하게 되기에 순차 탐색의 시간 복잡도는 $O(n)$입니다.
순차 탐색 알고리즘의 시간 복잡도는 $O(n)$이기에 탐색할 리스트의 길이가 길어지면 그에 비례하여 탐색 속도도 증가하지만, 탐색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있습니다.
이진 탐색 (Binary Search)
이진 탐색 방법
정렬된 배열을 탐색할 때는 이진 탐색이 가장 적합합니다. 이진 탐색은 Up Down 게임과 같은 매커니즘을 가지고 있습니다. 어떤 배열에서 특정 값을 찾으려할 때, 배열을 반으로 쪼개어 찾고자 하는 값이 왼쪽에 있는지 오른쪽에 있는지를 찾아 탐색 범위를 반으로 좁힙니다. 이를 원하는 값을 찾을 때까지 반복하여 탐색을 진행하는 방법입니다.
이진 탐색은 비교가 이루어질 때마다 탐색 범위가 급속도로 줄어들어 매우 빠른 탐색을 진행할 수 있습니다. 그러나 이진 탐색을 사용하기 위해서는 반드시 배열이 "정렬"되어 있어야 합니다. 그렇기에 추가되거나 삭제되지 않고 변하지 않는 고정된 데이터에서 탐색을 해야할 때 유용합니다.
이진 탐색 구현 (C언어)
#include <stdio.h>
#include <time.h>
#define MAX_ELEMENTS 10000000L
int list[MAX_ELEMENTS];
// 순환 호출 방법
int search_binary(int key, int low, int high) {
int middle;
if (low <= high) {
middle = (low + high) / 2;
if (key == list[middle]) // 탐색 성공
return middle;
else if (key < list[middle]) // 왼쪽 부분 리스트 탐색
return search_binary(key, low, middle - 1);
else // 오른쪽 부분 리스트 탐색
return search_binary(key, middle + 1, high);
}
return -1; // 탐색 실패
}
// 반복적인 방법
int search_binary2(int key, int low, int high)
{
int middle;
while (low <= high) { // 아직 숫자들이 남아 있으면
middle = (low + high) / 2;
if (key == list[middle])
return middle;
else if (key > list[middle])
low = middle + 1;
else
high = middle - 1;
}
return -1; // 발견되지 않음
}이진 탐색의 시간 복잡도 분석
이진 탐색은 탐색을 진행할 때마다 탐색 범위가 반으로 좁혀지고, 탐색 범위가 더 이상 줄일 수 없는 1이 될 때까지 진행합니다. 이를 수식으로 나타내어 시간 복잡도를 알아보겠습니다.
$n$개의 원소 중 특정 원소를 탐색하고자 할 때, 탐색 범위가 1이 될 때의 탐색 횟수를 $k$라고 하면 $n / 2^k = 1$이 됩니다. 따라서 $k = \log_{2}n$임을 알 수 있습니다. 그렇기에 이진 탐색의 시간 복잡도는 $(O(\log_{2}n))$이 됩니다.
이진 탐색 트리
지금까지 이진 탐색을 알아보았는데, 이진 트리 기반의 탐색을 위한 자료구조인 이진 탐색 트리에 대해서 간단히 알아보고 넘어가도록 하겠습니다.
이진 탐색 트리는 이진 탐색 트리의 성질을 만족하는 이진 트리입니다. 이진 탐색 트리의 정의는 다음과 같습니다.
- 모든 원소의 키는 유일한 키를 가진다.
- 왼쪽 서브 트리의 키들은 루트 키보다 작다.
- 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
찾고자 하는 키 값이 이진 트리의 루트 노드의 키값과 비교했을 때 루트 노드보다 작으면 왼쪽 서브트리에 있고, 루트 노드보다 크면 오른쪽 서브트리에 있음을 알 수 있습니다. 이러한 이진 탐색 트리의 성질을 이용해 이진 트리 알고리즘을 쉽게 사용할 수 있습니다.
색인 순차 탐색 (Indexed Sequential Search)
색인 순차 탐색 방법
색인 순차 탐색은 "인덱스(Index)"라는 테이블을 사용해 탐색의 효율을 높이는 탐색 기법입니다. 인덱스 테이블에 m개의 항목이 있고 주 자료 리스트의 데이터 수가 n이라면 각 인덱스 항목은 주 자료 리스트의 n/m번째 데이터를 가지게 됩니다. 다음의 그림을 통해서 이해해보도록 합시다. 색인 순차 탐색 또한 정렬된 배열에서만 사용할 수 있기에, 인덱스 테이블과 주 자료 리스트는 반드시 정렬되어 있어야 합니다.
색인 순차 탐색 알고리즘은 탐색을 진행할 때, 먼저 인덱스 테이블에서 index[ i ] <= key < index[ i+1 ]을 만족하는 항목을 찾습니다. 그 후 인덱스 테이블에서 조건을 만족하는 항목으로부터 주 자료 리스트에서 순차 탐색을 시작합니다. 이렇게 하면 일반적 순차 탐색보다 훨씬 빠르게 리스트에서 탐색을 수행할 수 있게 됩니다.
색인 순차 탐색 구현 (C언어)
#include <stdio.h>
#define MAX_SIZE 1000
#define INDEX_SIZE 10
int n=9;
int list[MAX_SIZE] = {3, 9,15, 22, 31, 55, 67, 88, 91};
typedef struct {
int key;
int index;
} itable;
itable index_list[INDEX_SIZE]={ {3,0}, {15,3}, {67,6} };
int seq_search(int key, int low, int high)
{
int i;
for(i=low; i<=high; i++)
if(list[i]==key)
return i; /* 탐색에 성공하면 키 값의 인덱스 반환 */
return -1; /* 탐색에 실패하면 -1 반환 */
}
/* INDEX_SIZE는 인덱스 테이블의 크기,n은 전체 데이터의 수 */
int index_search(int key)
{
int i, low, high;
/* 키 값이 리스트 범위 내의 값이 아니면 탐색 종료 */
if(key<list[0] || key>list[n-1])
return -1;
/* 인덱스 테이블을 조사하여 해당키의 구간 결정 */
for(i=0; i<INDEX_SIZE; i++)
if(index_list[i].key<=key &&
index_list[i+1].key>key)
break;
if(i==INDEX_SIZE){ /* 인덱스테이블의 끝이면 */
low = index_list[i-1].index;
high = n;
}
else{
low = index_list[i].index;
high = index_list[i+1].index;
}
/* 예상되는 범위만 순차 탐색 */
return seq_search(key, low, high);
}색인 순차 탐색의 시간 복잡도 분석
색인 순차 탐색은 인덱스 테이블의 크기에 따라 탐색 성능이 좌우됩니다. 즉, 인덱스 테이블의 크기가 커지면 인덱스 테이블의 탐색 시간을 증가되고, 인덱스 테이블의 크기가 작아지면 주 자료 리스트에서 탐색 시간이 증가됩니다.
인덱스 테이블의 크기를 m, 주 자료 리스트의 크기를 n이라고 하면 색인 순차 탐색의 시간 복잡도는 $O(m + n)$이 됩니다.
보간 탐색
보간 탐색 방법
보간 탐색은 사전을 찾는 방법을 생각하면 이해하기가 쉽습니다. 예를 들어 영어 사전으로 "God"이라는 단어를 찾을 때 a, b, c ... 이렇게 찾는 것이 아니라 바로 "G"챕터에 가서 찾듯이 보간 탐색도 마찬가지입니다.
보간 탐색은 탐색키가 존재할 위치를 예측하여 탐색하는 방법입니다. 이진 탐색과 달리 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색합니다. 이진 탐색에서 탐색 위치는 항상 $(low + high) /2 $이나 보간 탐색에서의 탐색 위치는 다음과 같습니다.
$$\frac{(k - list[low])}{list[high] - list[low]} \times (high - low) + low$$
k는 탐색하고자 하는 키의 값, low와 high는 각각 탐색할 범위의 최소&최대 인덱스 값을 의미합니다. 보간 탐색에서 가장 유의해야 할 점은 계산하여 나온 탐색 위치의 값은 일반적으로 실수인데, 이 실수를 정수로 변환해야 합니다. 일반적으로 소수점 이하를 버리는 방식으로 진행합니다.
보간 탐색 구현 (C언어)
#include <stdio.h>
#define MAX_SIZE 1000
int list[MAX_SIZE];
int search_interpolation(int key, int n)
{
int low, high, j;
low = 0;
high = n-1;
while ((list[high] >= key) && (key > list[low])){
j = ((float)(key-list[low]) / (list[high]-list[low]) *
(high-low) ) + low;
if( key > list[j] ) low = j+1;
else if (key < list[j]) high = j-1;
else low = j;
}
if (list[low] == key) return(low); //found(r[low])
else return -1; // notfound(key)
}보간 탐색의 시간 복잡도 분석
많은 데이터들이 고르게 분포되어 있다면 이진 탐색보다 보간 탐색이 더 짧은 평균 탐색 시간을 가집니다. 그러나 반대로 고르지 못한 데이터들을 검색한다면 시간이 좀 더 걸릴 수 있습니다. 보간 탐색의 시간 복잡도는 이진 탐색과 비슷한 $O(\log_{2}n)$을 가집니다.
탐색 알고리즘 비교
탐색 알고리즘을 선택할 때는 "자료가 정렬되어 있는가?"를 고려해야 하며, "내가 사용하는 자료구조가 삽입과 삭제가 용이한가? 또는 어려운가?"를 고려해야 합니다.
| 알고리즘 | 최악의 경우 | 평균적인 경우 | |||
| 탐색 | 삽입 | 탐색 | 삽입 | ||
| 순차 탐색 (정렬되지 않은 연결 리스트 사용) |
$N$ | $N$ | $N/2$ | $N$ | |
| 이진 탐색 (정렬된 배열) |
$\log N$ | $N$ | $\log N$ | $N/2$ | |
| 이진 탐색 트리 (정렬된 이진 트리) |
$N$ | $N$ | $\log N$ | $\log N$ | |
