탐색 - 1. 탐색(Search) 알고리즘 개요

📌 1. 탐색(Search) 알고리즘 개요

---

1.1 탐색 알고리즘이란?

탐색(Search) 알고리즘은 주어진 데이터에서 원하는 값을 찾는 과정을 의미합니다. 일반적으로 배열(Array), 연결 리스트(Linked List), 트리(Tree), 해시 테이블(Hash Table), 그래프(Graph)와 같은 자료구조에서 특정 값을 찾아야 할 때 탐색 알고리즘을 사용합니다.

💡 예제

• 전화번호부에서 특정 사람의 전화번호를 찾기
• 파일 시스템에서 특정 파일을 검색하기
• 데이터베이스에서 특정 정보를 검색하기

탐색 알고리즘을 선택할 때는 데이터의 크기, 정렬 여부, 검색 속도 등을 고려해야 합니다.

---

1.2 탐색 알고리즘의 종류 및 분류

탐색 알고리즘은 크게 다음과 같이 분류할 수 있습니다.

(1) 순차 탐색 (Linear Search)

• 데이터를 처음부터 끝까지 순차적으로 하나씩 비교하며 원하는 데이터를 찾는 방식
• 시간 복잡도: 최악의 경우 O(n)
• 장점: 구현이 간단하며 정렬되지 않은 데이터에서도 사용할 수 있음
• 단점: 데이터 크기가 커질수록 성능이 떨어짐

💡 예제:
학생 명단에서 특정 학생을 찾을 때, 처음부터 하나씩 확인하는 방식

---

(2) 이진 탐색 (Binary Search)

• 정렬된 데이터에서 중간값을 기준으로 탐색 범위를 절반씩 줄여가며 찾는 방식
• 시간 복잡도: 최악의 경우 O(log n)
• 장점: 순차 탐색보다 훨씬 빠름
• 단점: 데이터를 정렬해야 함

💡 예제:
책의 목차에서 특정 단어를 찾을 때, 중간을 먼저 보고 좌우를 선택하는 방식

---

(3) 해싱(Hashing)

• 해시 함수(Hash Function)를 사용하여 데이터를 특정한 위치에 빠르게 저장하고 검색하는 방식
• 시간 복잡도: 평균적으로 O(1)
• 장점: 매우 빠른 검색 가능
• 단점: 충돌(Collision) 문제가 발생할 수 있으며, 메모리를 더 사용할 수 있음

💡 예제:
딕셔너리(Dictionary)에서 단어를 찾을 때, 첫 글자의 알파벳으로 빠르게 접근하는 방식

---

(4) 그래프 탐색 (Graph Search)

그래프 구조에서 데이터를 탐색하는 방식이며, 대표적으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

• 깊이 우선 탐색(DFS, Depth First Search)
  • 한 방향으로 끝까지 탐색한 후, 다른 경로를 탐색하는 방식
  • 예제: 미로 찾기, 백트래킹 알고리즘
• 너비 우선 탐색(BFS, Breadth First Search)
  • 가까운 노드부터 차례로 탐색하는 방식
  • 예제: 최단 경로 찾기 (네트워크 연결, 길 찾기)

---

1.3 시간 복잡도와 효율성 개념 소개

탐색 알고리즘의 성능을 평가할 때 시간 복잡도(Time Complexity) 개념이 중요합니다.

탐색 알고리즘	평균 시간 복잡도	최악 시간 복잡도
순차 탐색 (Linear Search)	O(n)	O(n)
이진 탐색 (Binary Search)	O(log n)	O(log n)
해시 탐색 (Hashing)	O(1)	O(n) (충돌 발생 시)
DFS/BFS (그래프 탐색)	O(V + E)	O(V + E)

시간 복잡도 예제

• O(1) → 매우 빠름 (해시 탐색)
• O(log n) → 빠름 (이진 탐색)
• O(n) → 데이터가 많을수록 느려짐 (순차 탐색)
• O(n²), O(2ⁿ) → 매우 느림 (비효율적인 탐색)

예를 들어, 100만 개의 데이터가 있을 때:

• O(n): 1,000,000번 검사
• O(log n): 약 20번 검사 (100만을 2로 나눠서 1이 될 때까지)

이처럼 탐색 알고리즘을 선택할 때 효율적인 알고리즘을 적용하는 것이 중요합니다.

---

1.4 탐색과 정렬의 관계

• 이진 탐색(Binary Search)은 정렬된 데이터에서만 동작 가능
  → 따라서, 이진 탐색을 사용하려면 먼저 데이터를 정렬해야 함
• 해싱(Hashing)은 정렬과 상관없이 검색이 가능하지만, 공간 복잡도가 높을 수 있음
• 정렬 알고리즘을 먼저 실행하면 탐색이 훨씬 빨라질 수 있음
  → 예: 선형 탐색(O(n))보다 이진 탐색(O(log n))이 훨씬 빠름

예제

1. 정렬되지 않은 데이터 → 선형 탐색(Linear Search)
2. 정렬된 데이터 → 이진 탐색(Binary Search)
3. 데이터가 많을 경우 → 해싱(Hashing) 사용

---

🔍 실습: C에서 배열을 생성하고 기본적인 값을 출력하는 코드 작성

초보자를 위한 간단한 배열 생성 및 출력 코드입니다.

#include <stdio.h>

int main() {
    // 배열 선언 및 초기화
    int numbers[] = {10, 20, 30, 40, 50};
    int size = sizeof(numbers) / sizeof(numbers[0]); // 배열 크기 계산

    // 배열 요소 출력
    printf("배열 요소 출력:\n");
    for (int i = 0; i < size; i++) {
        printf("numbers[%d] = %d\n", i, numbers[i]);
    }

    return 0;
}

🔹 코드 설명

1. 배열 선언: int numbers[] = {10, 20, 30, 40, 50};
2. 배열 크기 계산: sizeof(numbers) / sizeof(numbers[0])
3. 배열 출력: for 루프를 사용하여 배열 요소를 출력

📌 실행 결과

배열 요소 출력:
numbers[0] = 10
numbers[1] = 20
numbers[2] = 30
numbers[3] = 40
numbers[4] = 50

이 코드에서 기본적인 배열의 개념을 익힌 후, 탐색 알고리즘(선형 탐색, 이진 탐색 등)을 추가하여 학습을 확장할 수 있습니다.

---

💡 마무리 및 정리

• 탐색 알고리즘은 데이터에서 특정 값을 찾는 과정이다.
• 종류: 선형 탐색, 이진 탐색, 해싱, 그래프 탐색(DFS, BFS) 등
• 효율성을 위해 시간 복잡도 개념을 이해해야 한다.
• 탐색과 정렬은 밀접한 관계가 있으며, 이진 탐색을 사용하려면 정렬이 필수이다.
• C언어에서 배열을 활용하여 탐색 알고리즘을 구현할 수 있다.