[알고리즘] C++로 이해하는 검색 알고리즘(선형 검색, 이진 검색, 해시법 등)

참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)

---

☑️ C++로 이해하는 검색 알고리즘

검색 알고리즘은 데이터 집합에서 특정 항목이나 값을 찾기 위해 사용하는 알고리즘이다. 모든 프로그래밍 분야에서 기본적이고 필수적인 알고리즘으로, C++에서는 find 함수를 통해서 검색 알고리즘을 제공하고 있다. 

 

검색 알고리즘은 다양한 방법이 있는데 데이터 집합의 성격에 따라서 알고리즘을 선택하는 것이 중요하다.

 

1️⃣ 선형 검색 (Linear Search)

가장 기본적인 알고리즘은 선형 검색이다. 선형 검색은 배열이나 리스트의 처음부터 끝까지 순차적으로 데이터를 검사하여 원하는 값을 찾는다. 구현이 간단하고 정렬되지 않은 데이터에서도 사용 가능하므로, 많은 분야에서 사용된다. 다만, 큰 데이터 집합에서 사용할 경우 찾는 효율이 좋지 않다.

선형 검색의 예시

 

📌 선형 검색 예제 코드(C++)

#include <iostream>
#include <vector>

template<typename T>
int linearSearch(const std::vector<T>& arr, const T& target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;  // 찾은 경우 인덱스 반환
        }
    }
    return -1;  // 못 찾은 경우 -1 반환
}

int main() {
    std::vector<int> numbers = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
    int target = 50;

    int result = linearSearch(numbers, target);

    if (result != -1) {
        std::cout << "값 " << target << "은(는) 인덱스 " << result << "에 있습니다." << std::endl;
    }
    else {
        std::cout << "값 " << target << "은(는) 배열에 없습니다." << std::endl;
    }

    return 0;
}

 

📌 선형 검색의 시간 복잡도

최선의 경우	O(1)
평균	O(n)
최악의 경우	O(n)

 

평균과 최악의 경우가 동일하게 O(n)으로 표기되어 있다. 선형 검색의 평균 시간 복잡도는 정확하게 O(n/2)를 가진다. 하지만, 빅오 표기법에서는 상수 계수가 무시되므로 O(n)으로 작성한다.

 

 

2️⃣ 이진 검색 (Binary Search)

이진 검색은 정렬된 데이터 집합에서만 사용 가능한 알고리즘으로 분할 정복(Divide and Conquer) 방식을 사용한다. 검색 범위를 절반씩 줄여나가는 방식으로 원하는 값을 찾는다. 선형 검색보다 빠르게 검색할 수 있다는 장점을 가진다. 큰 데이터 집합에서 효율적으로 동작한다.

이진 검색의 예시

위 사진은 오름차순으로 정렬되어 있는 배열로, 값 5를 검색하는 과정을 보여준다.

1. 배열의 중앙 원소 4에 접근한다.

2. 찾는 값은 5로, 4보다 더 큰 값을 가지므로, 검색하지 않은 배열의 남은 공간에서 중앙 원소에 접근한다(=6)

3. 값을 찾는다.

 

📌 이진 검색 예제 코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>  

template<typename T>
int binarySearch(const std::vector<T>& arr, const T& target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;  

        if (arr[mid] == target) {
            return mid;  // 찾은 경우
        }

        if (arr[mid] < target) {
            left = mid + 1;  // 오른쪽 절반 검색
        }
        else {
            right = mid - 1;  // 왼쪽 절반 검색
        }
    }

    return -1;  // 못 찾은 경우
}

template<typename T>
int binarySearchRecursive(const std::vector<T>& arr, const T& target, int left, int right) {
    if (left > right) {
        return -1;  // 기저 사례: 못 찾음
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;  // 찾은 경우
    }

    if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);  // 오른쪽 검색
    }
    else {
        return binarySearchRecursive(arr, target, left, mid - 1);  // 왼쪽 검색
    }
}

int main() {
    std::vector<int> numbers = { 10, 30, 40, 45, 70, 80, 85, 90, 100 };
    int target = 80;

    // 반복적 이진 검색
    int result1 = binarySearch(numbers, target);

    if (result1 != -1) {
        std::cout << "반복적 이진 검색: 값 " << target << "은(는) 인덱스 " << result1 << "에 있습니다." << std::endl;
    }
    else {
        std::cout << "반복적 이진 검색: 값 " << target << "은(는) 배열에 없습니다." << std::endl;
    }

    // 재귀적 이진 검색
    int result2 = binarySearchRecursive(numbers, target, 0, numbers.size() - 1);

    if (result2 != -1) {
        std::cout << "재귀적 이진 검색: 값 " << target << "은(는) 인덱스 " << result2 << "에 있습니다." << std::endl;
    }
    else {
        std::cout << "재귀적 이진 검색: 값 " << target << "은(는) 배열에 없습니다." << std::endl;
    }

    return 0;
}

 

📌 이진 검색의 시간 복잡도

최선의 경우	O(log n)
평균
최악의 경우

 

 

3️⃣ 해시법 (Hashing)

해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 의미한다. 즉, 해시 함수를 사용해서 Key 값을 배열 인덱스로 변환하는 방법이다. 이상적인 경우에 O(1)의 시간 복잡도로 검색이 가능하다.

해시법 예시

📌 해시 함수 (Hash Function)

해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 함수다. 쉽게 나타내면 키를 해시 값으로 변환하는 과정을 말한다. 좋은 해시 함수는 균일 분포, 결정성, 효율성, 충돌 최소화 등의 특성을 가진다.

 

📌 해시 충돌 (Hash Collision)

해시 충돌은 서로 다른 두 개 이상의 키가 해시 함수에 의해 같은 해시 값으로 매핑되는 상황을 의미한다. 해시 충돌은 해시 테이블의 크기가 제한되어 있고 키의 범위가 더 클 때 필연적 발생한다. 해시 충돌이 발생하는 경우 2가지 방법(체인법, 오픈 주소법)을 사용해서 해결할 수 있다.

ChatGPT - 해시 충돌을 이해할 수 있는 그림을 그려줘!

▶️ 체인법 (Chaining)

오픈 해시법(Open Hashing)으로도 불리는 체인법은 해시값이 같은 데이터를 체인(chain) 모양의 Linked List로 연결하는 방법을 의미한다. Linked List를 사용함으로서 같은 해시 값을 가진 여러 항목을 저장할 수 있다.

 

▶️ 오픈 주소법 (Open Addressing)

모든 Key-Value 쌍을 해시 테이블 배열 자체에 직접 저장하는 방식이다. 해시 충돌이 발생했을 때, 재해시(rehashing)를 수행하면서 비어있는 슬롯을 찾아 저장한다. 순차적으로 다음 슬롯을 검사하는 선형 탐사법(Linear Probing), 충돌이 발생한 다음 위치를 제곱 간격으로 탐색하는 이차 탐사법(Quadratic Probing) 등을 사용한다.