[2주차 TIL] KnockOn Bootcamp Pre.Rev : 탐색 알고리즘

탐색 알고리즘

탐색알고리즘이란 데이터 구조에서 특정요소를 찾거나, 조건에 맞는 요소를 검색하기 위해 사용되는 알고리즘이다.

순차탐색

데이터를 처음부터, 끝까지 하나씩 비교하며, 찾는 방법으로 데이터가 정렬되지 않았거나, 크기가 작을 때 유용하다.

• 시간 복잡도
  • 최선 : O(1) (첫번째 요소가 찾고자 하는 데이터일경우)
  • 최악 : O(n) (찾고자 하는 데이터가 맨 마지막에 있어 모든 요소를 한번씩 확인해야 하는 경우)

이진탐색

정렬된 데이터에서 중간 값을 기준으로 검색 범위를 반씩 줄여가며, 탐색하는 것으로 데이터가 정렬되어 있을 때, 빠르게 작동한다.

• 시간 복잡도 : O(log n)

Hashing

데이터를 해시 테이블에 저장하고, 키를 기반으로 직접 접근하는 것으로, 빠른 탐색이 필요한 경우 사용

• 시간 복잡도
  • 최선 : O(1)
  • 최악 : O(n) (해쉬 충돌 시)

깊이 우선 탐색

그래프나 트리에서 한 경로를 끝까지 탐색한 뒤, 다음 경로로 이동한다.

그래프의 모든 경로를 탐색하거나 특정 조건의 경로를 찾을 때, 사용

• 시간 복잡도 : O(V+E) (V : 정점, E : 간선)

너비 우선 탐색

그래프나 트리에서 현재 레벨의 모든 정점을 방문한 뒤, 다음 레벨로 이동한다.

최단 경로를 찾거나 단계별로 탐색할 때 사용

• 시간 복잡도 : O(V+E) (V : 정점, E : 간선)

실습

순차탐색

//sequential search
#include<stdio.h>
#include<stdlib.h>

int sequential_search(int arr[],int size,int data) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == data) {
            return i;
        }
    }
    return -1;
}

int main() {
    int data = 0;
    int arr[] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
    int size = sizeof(arr)/sizeof(int);
    printf("원하는 숫자를 쓰시오 : ");
    scanf_s("%d", &data);
    int i = sequential_search(arr, size, data);
    if (i != -1) {
        printf("%d는 %d번째 위치에 존재합니다.\n",data,i+1);
    }
    else {
        printf("%d는 존재하지 않습니다.\n",data);
    }
    return 0;
}

이진탐색

//binary search
#include <stdio.h>
#include <stdlib.h>

int binary_search(int arr[], int left, int right, int data) {
    if (left > right) {
        return -1; // 탐색 실패
    }

    int mid = left + (right - left) / 2; // 중간값 계산

    if (arr[mid] == data) {
        return mid; // 값을 찾음
    }
    else if (arr[mid] > data) {
        return binary_search(arr, left, mid - 1, data); // 왼쪽 절반 탐색
    }
    else {
        return binary_search(arr, mid + 1, right, data); // 오른쪽 절반 탐색
    }
}

int main() {
    int data;
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("원하는 숫자를 쓰시오: ");
    scanf_s("%d", &data);

    int result = binary_search(arr, 0, size - 1, data);

    if (result != -1) {
        printf("%d는 %d번째 위치에 존재합니다.\n", data, result + 1);
    }
    else {
        printf("%d는 존재하지 않습니다.\n", data);
    }

    return 0;
}

끝.