CS/알고리즘

[알고리즘] 탐색 알고리즘 기본 (선형 탐색, 이진 탐색, 해시 탐색)

청월누리 2025. 2. 16. 23:04

많은 탐색 알고리즘 중 기본이라고 할 수 있는 선형 탐색, 이진 탐색, 그리고 해시를 활용한 탐색에 대해 정리한 글입니다.

탐색의 기본 개념

정의

  • 주어진 데이터 구조 안에서 특정 값(key) 또는 조건을 만족하는 데이터를 찾아내는 과정

목표

  • 해당 값이 존재하는지 확인 (존재 여부)
  • 존재한다면 그 위치(인덱스, 노드 포인터 등)를 반환 (위치 정보)
  • 존재하지 않는다면 탐색 실패 처리

성능 척도

  • 시간 복잡도 : 탐색에 걸리는 평균 / 최악 / 최선 연산 횟수 확인
  • 공간 복잡도 : 추가 메모리 사용량 (보조 자료구조가 필요 여부 등)
  • 구현 난이도 : 자료 구조의 복잡도 & 코드 구현의 편리성

분류

  • 배열 기반 탐색 : 선형 탐색, 이진 탐색 등
  • 연결 리스트 기반 탐색
  • 트리 기반 탐색 : 이진 검색 트리, 트리 순회, 자가 균형 트리 등
  • 그래프 기반 탐색 : BFS (너비 우선 탐색), DFS (깊이 우선 탐색), 최단 경로 탐색 등
  • 해시 탐색

선형 탐색 (Linear Search)

기본 개념

  • 정렬 여부와 무관하게 배열의 첫 번째 원소부터 차례대로 확인하며, 원하는 값(key)을 찾는 가장 단순한 방식
  • 원하는 값을 찾으면 해당 인덱스를 반환하고 종료
  • 끝까지 탐색한 결과 원하는 값이 없으면 실패를 알리는 값(ex. -1)을 반환

알고리즘 동작 과정

  1. 배열의 인덱스 0부터 시작
  2. 현재 인덱스의 값이 찾는 값(key)과 일치하는지 비교
  3. 일치하면 해당 인덱스를 반환 후 탐색 종료
  4. 일치하지 않으면 인덱스를 1 증가시켜 다음 원소 검사
  5. 배열의 끝까지 확인해도 찾는 값이 없으면 -1 등으로 표시하고 탐색 종료

시간 복잡도

  • 평균 / 최악 : $ O(N) $ - N개의 원소를 모두 확인해야 찾는 경우
  • 최선 : $ O(1) $ - 찾는 값이 배열의 첫 번쨰 원소라면 한 번 비교로 종료

장점과 단점

장점

  • 구현이 매우 간단하며 추가 메모리 불필요
  • 정렬 여부나 특수한 전처리 불필요

단점

  • N이 커지만 탐색 시간이 길어짐
  • 매 탐색마다 최대 N번 비교해야 하므로 대용량 데이터에는 비효율적

코드 예시

C++ 코드 예시

#include <iostream>
#include <vector>
using namespace std;

// 선형 탐색 함수
int linearSearch(const vector<int>& arr, int key) {
    for(int i = 0; i < (int)arr.size(); i++) {
        if(arr[i] == key) {
            return i;  // 찾는 값 발견 시 인덱스 반환
        }
    }
    return -1;  // 못 찾으면 -1
}

int main() {
    vector<int> arr = {10, 3, 7, 15, 8};
    int key = 15;
    int index = linearSearch(arr, key);

    if(index != -1)
        cout << "Key " << key << " found at index " << index << endl;
    else
        cout << "Key " << key << " not found" << endl;

    return 0;
}

Python 코드 예시

def linear_search(arr, key):
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    return -1

if __name__ == "__main__":
    arr = [10, 3, 7, 15, 8]
    key = 15
    index = linear_search(arr, key)

    if index != -1:
        print(f"Key {key} found at index {index}")
    else:
        print(f"Key {key} not found")

이진 탐색 (Binary Search)

기본 개념

  • 이진 탐색은 배열이 정렬되어 있어야 적용 가능한 탐색 알고리즘
  • 배열의 중간(mid) 값을 확인해 찾는 값(key)이 그 보다 작으면 왼쪽 구간만, 크면 오른쪽 구간만 탐색
  • 매 비교마다 탐색 구간이 절반으로 줄어들므로 $ O(\log N) $의 효율적인 시간 복잡도

알고리즘 동작 과정

오름차순으로 정렬된 배열을 가정한 동작 과정

  1. left = 0, right = N - 1 (초기 탐색 범위) 설정
  2. mid = (left + right) // 2 (중간 인덱스 계산)
  3. arr[mid]와 key 비교
    • 같으면 mid 반환 (탐색 성공)
    • arr[mid] > key이면, 오른쪽 부분은 필요 없음 >> right = mid - 1
    • arr[mid] < key이면, 왼쪽 부분은 필요 없음 >> left = mid + 1
  4. left <= right인 동안 2~3 과정 반복
  5. 찾지 못하면 실패(ex. -1) 반환

시간 복잡도

  • 평균 / 최악 : $ O(\log N) $ - 탐색 범위가 매번 절반씩 감소
  • 최선 : $ O(1) $ - 찾는 값이 배열의 중간 값인 경우

장점과 단점

장점

  • 정렬된 배열에 대해 매우 빠른 탐색 가능
  • 구현이 비교적 단순하며, 재귀 또는 반복 모두로 쉽게 작성 가능

단점

  • 배열이 정렬되어 있지 않다면 사용 불가 >> 배열 정렬 비용( $ O(N \log N) $ )이 추가될 수 있음
  • 데이터를 삽입 / 삭제할 때마다 정렬 상태가 깨질 수 있으므로, 동적 자료 처리에서는 비효율적

코드 예시

C++ 코드 예시

#include <iostream>
#include <vector>
#include <algorithm> // sort

using namespace std;

int binarySearch(const vector<int>& arr, int key) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = (left + right) / 2;  // (left + right) >> 1; 로도 가능
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1; // not found
}

int main() {
    vector<int> arr = {15, 3, 8, 2, 10};
    sort(arr.begin(), arr.end());  // 이진 탐색을 위해 정렬
    int key = 8;

    int index = binarySearch(arr, key);
    if(index != -1)
        cout << "Key " << key << " found at index " << index << endl;
    else
        cout << "Key " << key << " not found" << endl;
    return 0;
}

Python 코드 예시

def binary_search(arr, left, right, key):
    if left > right:
        return -1

    mid = (left + right) // 2
    if arr[mid] == key:
        return mid
    elif arr[mid] > key:
        return binary_search(arr, left, mid - 1, key)
    else:
        return binary_search(arr, mid + 1, right, key)

if __name__ == "__main__":
    arr = [15, 3, 8, 2, 10]
    arr.sort()  # 이진 탐색을 위해 정렬
    key = 8

    index = binary_search(arr, 0, len(arr) - 1, key)
    if index != -1:
        print(f"Key {key} found at index {index}")
    else:
        print(f"Key {key} not found")

해시(Hash)를 활용한 탐색

기본 개념

  • 해시(Hash) 탐색은 Key를 해시 함수를 통해 배열의 인덱스로 직접 매핑하여 평균 $ O(1) $에 가까운 접근 속도를 얻는 방식
  • 해시 탐색에서는 해시 함수, 해시 테이블, 충돌 해결 방식이 중요함
    • 해시 함수(hash function) : key를 적절히 분산해서 인덱스에 매핑하는 함수
    • 해시 테이블(hash table) : 해시 함수 결과값(인덱스)에 실제 데이터를 저장할 배열
    • 충돌(collision) 해결 방식 : 서로 다른 key가 같은 해시 인덱스를 가질 경우를 처리하는 방법

시간 복잡도

  • 평균 : $ O(1) $ - 충돌이 적고, 해시 함수가 균등 분포를 만들어낼 때
  • 최악 : $ O(N) $ - 모든 key가 한 인덱스로 충돌할 경우, 사실상 선형 탐색과 동일

충돌(Collision) 해결 방식

분리 연결법(Chaining)

  • 해시 테이블의 각 인덱스가 하나의 연결 리스트(또는 다른 자료구조)를 두어 해당 인덱스에 할당된 key들을 다 저장
  • 탐색 시 해시 인덱스의 리스트를 선형 탐색하여 key를 찾음
  • 장점 : 테이블이 꽉 차도(load factor가 높아져도) 개별 연결 리스트를 통해 어느 정도 확장 가능
  • 단점 : 연결 리스트를 위한 추가 메모리가 필요, 최악의 경우 $ O(N) $
// Pseudo code
Insert(table, key):
    index = HashFunction(key)
    table[index].insert(key)

Search(table, key):
    index = HashFunction(key)
    for element in table[index]:
        if element == key:
            return true
    return false

개방 주소법(Open Addressing)

  • 해시 테이블 자체 안에서 충돌이 발생하면 다른 비어있는 인덱스를 찾아서 저장하는 방식
  • 대표적으로 선형 탐사, 이차 탐사, 이중 해싱 등이 있음
    • 선형 탐사 (linear probing) : 충돌 시, (index + 1) % TableSize 식으로 한 칸식 이동하며 비어 있는 슬롯을 찾음
    • 이중 탐사 (quadratic probing) : (index + (i * i)) % TableSize 형태로 i를 늘려가며 슬롯을 찾음
    • 이중 해싱 (double hashing) : 두 개의 해시 함수를 사용해 충돌 시 2차 해시로 이동 폭을 결정'
// 선형 탐사 (linear probing) pseudo code
Insert(table, key):
    index = HashFunction(key)
    while table[index] is not empty:
        index = (index + 1) % TableSize
    table[index] = key

Search(table, key):
    startIndex = HashFunction(key)
    index = startIndex
    while table[index] != empty:
        if table[index] == key:
            return true
        index = (index + 1) % TableSize
        if index == startIndex: // 한 바퀴 돌면
            break
    return false
  • 개방 주소법은 테이블 내에서 추가 탐색을 하기 떄문에 충돌이 많아질수록 탐색 성능이 저하될 수 있음

코드 예시

C++ 코드 예시

분리 연결법(Chaining)을 간단하게 구현한 예시

#include <iostream>
#include <vector>
#include <list>
using namespace std;

class HashTable {
private:
    vector<list<int>> table;
    int size;

    // 간단한 해시 함수 (key % size)
    int hashFunction(int key) const {
        return key % size;
    }

public:
    // 생성자
    HashTable(int tableSize) : size(tableSize) {
        table.resize(tableSize);
    }

    // 삽입
    void insertKey(int key) {
        int index = hashFunction(key);
        table[index].push_back(key); 
    }

    // 탐색
    bool searchKey(int key) const {
        int index = hashFunction(key);
        // 분리 연결된 리스트를 순회하며 key 검사
        for (auto &element : table[index]) {
            if (element == key) {
                return true;
            }
        }
        return false;
    }
};

int main() {
    HashTable ht(10); // 해시 테이블 크기 10

    ht.insertKey(15);
    ht.insertKey(25);
    ht.insertKey(35); // 15, 25, 35 모두 index 5에 저장(key % 10)

    cout << boolalpha;
    cout << "Search 15: " << ht.searchKey(15) << endl; // true
    cout << "Search 7: " << ht.searchKey(7) << endl;   // false

    return 0;
}
  • hashFunction(key) = key % size는 매우 간단한 예시로, 실제로는 더 정교한 해시 함수를 사용해야 충돌을 줄일 수 있음
  • std::list<int> 대신 std::forward_list<int> 또는 다른 컨테이너를 활용할 수 있음
  • 해시 테이블 크기는 충돌 발생 가능성, 메모리 사용량 등을 고려하여 적절히 설정하고, 원소가 많아지는 경우 리사이징(Resize)과 재해싱(Rehash)을 수행하기도 함

비교 및 핵심 요약

탐색 방식 정렬 필요 여부 평균 시간 복잡도 최악 시간 복잡도 특징
선행 탐색 불필요 $ O(N) $ $ O(N) $ 구현이 가장 간단
데이터 정렬 필요 없음
이진 탐색 필요 $ O(\log N) $ $ O(\log N) $ 정렬된 배열 사용
동적 자료 변경 시 재정렬 필요
해시 탐색 불필요 $ O(1) $ $ O(N) $ 평균적으로 매우 빠름
해시 함수 품질과 충돌 해결 기법이 중요
  • 선형 탐색
    • 모든 경우에 사용 가능하지만 가장 느린 편
    • 자료가 작거나 한 두번 탐색할 때는 구현의 간단함이 장점 
  • 이진 탐색
    • 배열이 정렬되어 있을 때 빠른 탐색 가능
    • 삽임 및 삭제가 잦으면 매번 정렬(또는 정렬 상태 유지)이 부담
  • 해시 탐색
    • 평균 $ O(1) $로 가장 빠르지만 해시 함수 설계와 충돌 해결 기법이 중요
    • 최악엔 여전히 $ O(N) $일 수 있지만, 보통 성능이 우수해 많이 사용됨