탐색 - 11. 탐색 알고리즘 성능 비교 프로젝트

📌 11. 탐색 알고리즘 성능 비교 프로젝트

---

11.1 탐색 알고리즘 성능 비교 개요

탐색(Search) 알고리즘은 데이터에서 특정 값을 찾는 중요한 기법입니다.
각 탐색 알고리즘은 데이터 구조와 입력 크기에 따라 성능 차이가 발생합니다.

💡 목표:

• 동일한 데이터셋에서 여러 탐색 알고리즘을 실행하여 성능 비교
• 입력 크기 변화에 따른 실행 시간 분석
• 실생활 응용 사례 연구 (데이터베이스 검색, 웹 크롤링 등)

✔ 비교할 탐색 알고리즘:

1. 선형 탐색(Linear Search) vs 이진 탐색(Binary Search)
2. 해시 테이블(Hash Table) vs 선형 탐색(Linear Search)

---

11.2 탐색 알고리즘의 실생활 활용 사례

🔹 데이터베이스 검색

• SQL에서 인덱스(Index)를 사용하면 탐색 속도 향상
  • B-Tree 기반 탐색 (이진 검색 트리 응용)
  • 해싱 기반 탐색 (해시 인덱스 활용)

🔹 웹 크롤링 및 검색 엔진

• 문서 검색: 웹 페이지의 키워드 검색
  • 선형 탐색(O(n)) 대신 트라이(Trie)나 해시 테이블로 빠른 검색
• 검색 엔진: Google, Bing 등에서 역색인(Inverted Index) + 해싱을 사용하여 검색 최적화

🔹 AI 및 경로 탐색

• A 알고리즘*: 게임 개발에서 최적 경로 탐색
• 다익스트라 알고리즘: 네트워크 최단 경로 계산

---

11.3 실습: 탐색 알고리즘 성능 비교

1️⃣ 정렬된/정렬되지 않은 데이터에서 선형 탐색 vs 이진 탐색 비교

실험 목표

• 정렬되지 않은 배열에서는 선형 탐색만 가능
• 정렬된 배열에서는 이진 탐색이 훨씬 빠름 (O(log n) vs O(n))

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 선형 탐색
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

// 이진 탐색 (정렬된 배열 전용)
int binarySearch(int arr[], int left, int right, int target) {
    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;
}

// 비교 테스트 실행
void testSearchAlgorithms() {
    int size = 100000;
    int *arr = (int*)malloc(size * sizeof(int));

    // 데이터 초기화 (1~size 범위로 정렬)
    for (int i = 0; i < size; i++) {
        arr[i] = i + 1;
    }
    int target = size; // 마지막 요소 탐색

    clock_t start, end;
    double time_spent;

    // 선형 탐색 실행
    start = clock();
    int linearResult = linearSearch(arr, size, target);
    end = clock();
    time_spent = (double)(end - start) / CLOCKS_PER_SEC;
    printf("선형 탐색 실행 시간: %.6f 초\n", time_spent);

    // 이진 탐색 실행
    start = clock();
    int binaryResult = binarySearch(arr, 0, size - 1, target);
    end = clock();
    time_spent = (double)(end - start) / CLOCKS_PER_SEC;
    printf("이진 탐색 실행 시간: %.6f 초\n", time_spent);

    free(arr);
}

int main() {
    testSearchAlgorithms();
    return 0;
}

📌 실행 결과 예시

선형 탐색 실행 시간: 0.012345 초
이진 탐색 실행 시간: 0.000001 초

✔ 이진 탐색이 훨씬 빠름!
✔ 정렬된 데이터에서는 이진 탐색을 사용하는 것이 효율적

---

2️⃣ 해시 테이블(Hash Table) vs 선형 탐색(Linear Search) 성능 비교

실험 목표

• 해시 테이블(평균 O(1))과 선형 탐색(O(n))의 성능 차이 비교

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TABLE_SIZE 100000

// 해시 테이블 (간단한 체이닝 기법)
typedef struct Node {
    int key;
    struct Node* next;
} Node;

Node* hashTable[TABLE_SIZE] = {NULL};

// 해시 함수
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// 해시 테이블 삽입
void insert(int key) {
    int index = hashFunction(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// 해시 테이블 검색
int searchHashTable(int key) {
    int index = hashFunction(key);
    Node* current = hashTable[index];
    while (current) {
        if (current->key == key) return 1;
        current = current->next;
    }
    return 0;
}

// 비교 테스트 실행
void testHashTableVsLinearSearch() {
    int size = TABLE_SIZE;
    int *arr = (int*)malloc(size * sizeof(int));

    // 데이터 초기화
    for (int i = 0; i < size; i++) {
        arr[i] = i + 1;
        insert(i + 1); // 해시 테이블에도 삽입
    }
    int target = size; // 마지막 요소 탐색

    clock_t start, end;
    double time_spent;

    // 선형 탐색 실행
    start = clock();
    int linearResult = linearSearch(arr, size, target);
    end = clock();
    time_spent = (double)(end - start) / CLOCKS_PER_SEC;
    printf("선형 탐색 실행 시간: %.6f 초\n", time_spent);

    // 해시 테이블 탐색 실행
    start = clock();
    int hashResult = searchHashTable(target);
    end = clock();
    time_spent = (double)(end - start) / CLOCKS_PER_SEC;
    printf("해시 테이블 탐색 실행 시간: %.6f 초\n", time_spent);

    free(arr);
}

int main() {
    testHashTableVsLinearSearch();
    return 0;
}

📌 실행 결과 예시

선형 탐색 실행 시간: 0.015678 초
해시 테이블 탐색 실행 시간: 0.000002 초

✔ 해시 테이블이 훨씬 빠름!
✔ 대량의 데이터 검색에서는 해시 테이블을 사용하는 것이 효율적

---

📌 마무리 및 정리

비교 항목	선형 탐색	이진 탐색	해시 테이블
시간 복잡도	O(n)	O(log n)	O(1) (평균)
정렬 필요 여부	❌ 불필요	✅ 필요	❌ 불필요
검색 속도	느림	빠름	매우 빠름
데이터 크기 증가 시 영향	성능 저하	비교적 안정적	매우 효율적

💡 결론:

• 정렬되지 않은 데이터 → 해시 테이블이 가장 효율적
• 정렬된 데이터 → 이진 탐색이 선형 탐색보다 빠름
• 작은 데이터셋 → 선형 탐색도 가능하지만, 큰 데이터에서는 효율적인 탐색이 필요!