[c++] 알고리즘 개념공부 :: 탐색 (선형 탐색, 이진 탐색, 해시 탐색)

탐색

 탐색은 주어진 자료들 중 원하는 조건에 해당하는 자료를 찾는 과정이다. 컴퓨터에서 탐색은 자주 이루어지므로 효율적인 방식으로 수행하는 것이 중요하다.

 이전에 배웠던 '정렬'은 탐색을 수행할 수 있는 방법 중 하나이다. 정렬은 리스트를 하나의 기준으로 나타내기 위해서도 쓰이지만 원하는 자료를 빠르게 탐색하기 위해 쓰이기도 한다. 물론 굳이 정렬이 아니더라도 탐색을 수행할 수 있는 방법은 있다.

 

정렬 보기

 

앞으로 소개할 탐색은 다음의 4가지 종류이다.

1. 선형탐색

2. 이진탐색

3. 해시탐색

4. BST

   탐색을 위해서는 배열, 연결 리스트, 트리, 그래프 등 다양한 자료구조가 사용되며, 상황에 따라 맞춰서 사용하면 된다.

자료구조 보기

 

선형 탐색

 순차 탐색이라고도 불리는 선형 탐색은 가장 간단한 탐색 방법이다. 선형 탐색에서는 정렬되지 않은 초기 리스트를 처음부터 끝까지 차례로 검사한다.

 

 리스트에 있는 요소의 갯수를 n이라고 할 때, 순차탐색은 발견하는 순간 탐색을 마친다. 리스트에 원하는 요소가 있는 경우에는 평균적으로 (n+1)/2의 비교로 요소를 찾아낼 수 있지만, 리스트에 원하는 요소가 없을 경우에는 총 n+1 번의 비교 끝에 해당 요소가 없다는 점을 발견하게 된다. 따라서 순차탐색의 시간 복잡도는 O(n)이다.

 

구현

의사코드는 다음과 같다.

//value : 찾고자 하는 값
//index : 찾은 값의 위치

for i=0 to n:
    if arr[i] == value
        index = i
        break

 

c++로 구현한 코드는 다음과 같다.

int arr[9] = { 3,1,5,7,2,4,9,6,8 };
int arr_size = sizeof(arr) / sizeof(int);

int linearSearch(int target) {
    // 찾은 값의 index 반환, 없으면 -1 반환
    int result = -1;

    for (int i = 0; i < arr_size; i++) {
        if (arr[i] == target) {
            result = i;
            break;
        }
    }
    return result;
}

 

이진 탐색

 이분 탐색이라고도 불리는 이진 탐색은 정렬된 리스트에 적용하기 좋은 탐색 방법이다. 앞서 설명했듯이 탐색을 하는 방법에는 정렬도 속해있다고 했는데, 정렬 후 이진 탐색을 이용하게 되면 여러 번 낮은 시간 복잡도로 요소를 탐색할 수 있다. 물론 정렬의 시간복잡도까지 생각한다면 단순한 선형 탐색이 더 낫다고 생각할수도 있지만, 정렬은 리스트에 대해 한번만 수행되어도 되므로 반복적인 탐색을 생각한다면 정렬 후 이진 탐색 방법이 더 좋을 수도 있다.

 

 이진 탐색은 우선 주어진 리스트를 정렬하는 것에서 시작한다. 이후 정렬된 리스트의 가운데에 있는 요소와 찾고자하는 값을 비교한다. 대소관계에 따라 해당 요소가 맞는지, 아니면 왼쪽 리스트에 있는지 오른쪽 리스트에 있는지를 판단한다. 찾고자하는 값보다 가운데에 있는 요소가 더 작아서 더 큰 범위에서 찾아야한다면 해당 요소 오른쪽에 정렬되어있는 리스트를 가져와 위와같은 과정을 반복한다.

 

 리스트에 원하는 요소가 존재하지 않는 경우를 최악으로 생각해보면, 리스트의 요소를 1/2씩 줄여가므로 최악의 경우 lgn번의 비교가 필요하다. 따라서 이진 탐색의 시간복잡도는 O(lgn)이다.

 

구현

의사코드는 다음과 같다.

//value : 찾고자 하는 값
//index : 찾은 값의 위치

function binarySearch (start, end):
    if start == end 
        if value == arr[start]
            index = start
        else
            return


    mid := start + end / 2 
    if mid == value
        index = mid
        break
    else if mid > value
        binarySearch(start, mid)
    else if mid < value
        binarySearch(mid+1, end)
end

 

c++로 구현한 코드는 다음과 같다.

// 호출 예시
quickSort(arr, 0, arr_size);
cout << "이진 탐색 결과 : " << binarySearch(0, arr_size, 2) << endl;

// 구현 코드
int binarySearch(int start, int end, int target){
    if (end-start<=1) {
        if (target == arr[start])
            return start;
        return -1;
    }
    int result = -1;
    int mid = (int)((start + end) / 2);
    if (arr[mid] == target)
        result = mid;
    else if (arr[mid] > target)
        result = binarySearch(start, mid, target);
    else if (arr[mid] < target)
        result = binarySearch(mid + 1, end, target);

    return result;
}

 

보간 탐색

이진 탐색은 리스트에서 중간에 있는 요소를 기점으로 판단한다면, 보간 탐색은 요소가 있을 만한 인덱스를 예측해서 해당 인덱스에 있는 요소를 기점으로 판단하는 탐색 방법이다. 즉, 리스트를 불균등 분할하여 탐색하는 방법이다. 이미 정렬된 데이터를 가지고 하는 탐색이기 때문에 보간 탐색이 더 효율적일 수도 있다.

 

이진 탐색 트리 (BST)

자료구조 - 트리

 

 BST(Binary Search Tree)는 트리의 한 종류이자 이진탐색을 위한 방법 중 하나이다. 위에서는 배열을 사용한 리스트를 이용하여 이진탐색을 구현하였지만, 이번에는 연결리스트를 사용한 트리를 이용하여 이진 탐색 트리를 구현해보자. 리스트와 트리 모두 배열 또는 연결리스트로 구현할 수 있지만, 각각에 효율적인 방법으로 리스트는 배열을 사용하고 트리는 연결리스트를 사용하도록 구현하자.

 이진 탐색은 리스트(배열)를 사용하기 때문에 자료의 삽입 / 삭제가 매우 비효율적이다. 하지만 이진 탐색 트리는 트리(연결 리스트)를 사용해서 삽입 / 삭제가 효율적이다. 따라서 삽입 / 삭제가 빈번히 이루어진다면 이진 탐색 트리가 유리하다. 이진 탐색 트리는 즉 이진 탐색이라는 효율적인 알고리즘에 연결리스트라는 삽입 / 삭제에 효율적인 자료구조를 더한 형태이다. 아래의 포스팅으로 더 자세히 이해해보자.

BST

해시 탐색

(해시 링크)

해시 탐색은 해시 함수를 이용한 탐색 방법이다. 해시 함수란 원래 '임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수'를 일컫는데, 쉽게 말하면 다양한 형태의 데이터를 구분하기 쉽게 분류하는 함수이다.

 

 해시 함수를 거친 후 나오는 결과값으로 입력들을 분류하는 과정은 미리 준비해둔 상자(해시 테이블)에 입력들을 분류해서 담아둔다고 이해하면 된다. 이렇게 미리 상자에 담아두면 나중에 해당 요소를 찾고자 할 때 빠르게 찾을 수 있다.

해시 탐색은 해시 함수를 사용해 입력들을 분류/저장하는 작업이 먼저 필요하고, 그 후 요소를 탐색할 때는 찾고자하는 요소의 해시값을 이용해 빠르게 요소를 탐색할 수 있다.

 

 분류 저장하는 작업에서 주의할 점은 해시 함수에 의한 해시 값이 겹칠 수도 있다는 것이다. 이를 해시값 충돌이라고 하고, 해시 함수는 해시값 충돌이 빈번하게 일어날 수록 질이 안 좋다고 판단된다. 일반적으로 입력의 크기에 2배로 해시 값 배열을 준비하지만, 다른 입력에 대해서 해시 값이 겹치는 경우에는 배열의 다음 인덱스들을 훑으면서 비어있는 인덱스에 저장해야한다.

해시 값이 겹치는 경우에 해결하는 방법은 다양한다. 같은 해시 값에 해당하는 요소들을 연결 리스트로 만들어두는 방법도 있다. 이 글에서는 인덱스를 증가시키면서 비어있는 인덱스에 저장하는 방법을 사용한다.

해시 충돌 발생시 조사하게 되는 대체 칸을 번지 계열이라고 한다.

번지 계열이 겹쳐서 충돌이 일어나는 경우를 클러스터 라고 한다.

 그 후 요소를 탐색할 때도 처음에는 해시값을 이용해서 빠르게 요소를 탐색할 수 있지만, 해시값 충돌로 인해 다른 인덱스에 저장되어있을 수 있기 때문에 원하는 값과 일치하지 않는다면 결국 찾던 인덱스로부터 순차 탐색 해보아야한다. 따라서 해시 탐색은 해시 함수의 질이 좋을 때만 효율적으로 작동한다.

 

구현

#include <iostream>
#include <string>

using namespace std;

int hashFunction(int data) {
    // 해시 함수
	return data % 10;
}

void classifyData(int data, int* table) {
    // 데이터 분류 및 저장
	int hashValue = hashFunction(data);
	int flag = 0;
	while (hashValue<20) {
		if (table[hashValue] == -1) { // 해당 칸에 요소가 없으면
			table[hashValue] = data;
			flag = 1;
			break;
		}
		hashValue++; // 다음 칸으로 이동
	}
	if(!flag)
		cout << "저장 실패, 공간 부족" << endl;
}

bool searchData(int data, int* table) {
    // 데이터 탐색
	int hashValue = hashFunction(data);
	while (hashValue<20) {
		if (table[hashValue] == data) { // 발견했으면
			return true;
		}
		hashValue++;
	}
	return false;
}

void printHashTable(int* table) {
	for (int i = 0; i < 20; i++) {
		cout << table[i] << " ";
	}
	cout << endl;
}

int main() {
    // 주어진 input을 hashTable로 분류하고 탐색하는 프로그램
    
	int input[10] = { 41,24,35,26,12,33,44,5,2,1 };
	int hashTable[20];
	memset(hashTable, -1, sizeof(hashTable));
	
	for (int i = 0; i < 10; i++) {
		classifyData(input[i], hashTable);
	}
	printHashTable(hashTable);

	string result = searchData(33, hashTable) ? "있음" : "없음";
	cout << "33 탐색 : " + result << endl;

	int a; cin >> a;
}

 

특징

 해시 탐색에서는 원하는 요소를 탐색할 때 상수의 시간복잡도로 연산이 가능하다. 하지만 위에서 언급했듯이 해시 함수의 질이 좋지 않다면, 더 복잡해질 수도 있다.

또한 기존 입력의 2배 이상의 배열이 필요하므로 공간 복잡도 측면에서는 좋지 않은 선택이다.

---

참고 : https://pwnwiz.tistory.com/9