[2주차 TIL] KnockOn Bootcamp - 탐색 알고리즘

 

🔍 1. 탐색 알고리즘이란?

탐색(Search)은 데이터 집합에서 특정 값을 찾는 과정이다.
데이터의 양이 많아질수록 탐색에 걸리는 시간이 길어지므로, 효율적인 알고리즘을 사용하는 것이 중요합니다.

---

🔎 2. 순차 탐색 (Sequential Search)

✅ 개념

순차 탐색은 데이터를 처음부터 끝까지 하나씩 비교하여 원하는 값을 찾는 방법이야.
정렬되지 않은 데이터에서도 사용할 수 있어.

🧠 시간 복잡도

• 최선의 경우: O(1) (첫 번째 요소가 원하는 값일 때)
• 최악의 경우: O(n) (마지막 요소가 원하는 값이거나 없는 경우)
• 평균적인 경우: O(n)

💻 C언어 구현 예시

#include <stdio.h>

int sequential_search(int arr[], int size, int target) {
    for(int i = 0; i < size; i++) {
        if(arr[i] == target)
            return i; // 찾은 위치 반환
    }
    return -1; // 찾지 못한 경우
}

int main() {
    int data[] = {4, 2, 7, 1, 9, 5};
    int target = 7;
    int index = sequential_search(data, 6, target);

    if(index != -1)
        printf("찾는 값 %d는 인덱스 %d에 있습니다.\n", target, index);
    else
        printf("값을 찾을 수 없습니다.\n");

    return 0;
}

---

🔎 3. 이진 탐색 (Binary Search)

✅ 개념

이진 탐색은 정렬된 데이터에서 중간 값을 기준으로 탐색 범위를 반으로 줄여가며 원하는 값을 찾는 방법이야.
매우 빠른 탐색이 가능하지만, 데이터가 정렬되어 있어야 해.

🧠 시간 복잡도

• 모든 경우: O(log n)

💻 C언어 구현 예시

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while(low <= high) {
        int mid = (low + high) / 2;

        if(arr[mid] == target)
            return mid; // 찾은 위치 반환
        else if(arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1; // 찾지 못한 경우
}

int main() {
    int data[] = {1, 2, 4, 5, 7, 9};
    int target = 5;
    int index = binary_search(data, 6, target);

    if(index != -1)
        printf("찾는 값 %d는 인덱스 %d에 있습니다.\n", target, index);
    else
        printf("값을 찾을 수 없습니다.\n");

    return 0;
}

---

🧠 4. 정리

탐색 방법	정렬 필요 여부	시간 복잡도	특징
순차 탐색	필요 없음	O(n)	간단하지만 느릴 수 있음
이진 탐색	필요함	O(log n)	빠르지만 정렬 필요

---

💡 도전 과제

1. 위의 코드를 참고하여 사용자로부터 입력받은 숫자 배열에서 원하는 값을 찾는 프로그램을 작성해보자.
2. 이진 탐색을 사용하기 위해 버블 정렬이나 삽입 정렬을 이용하여 배열을 정렬한 후 탐색을 수행해보자.
3. 재귀 함수를 이용하여 이진 탐색을 구현해보자.