[TIL]탐색 알고리즘

탐색 알고리즘?

: 데이터 집합 내에서 특정 값을 찾는 과정을 효율적으로 수행하기 위한 알고리즘

---

1. 순차 탐색(Linear Search)

: 첫 번째 요소부터 마지막 요소까지 차례로 특정 값을 찾는 방법, 정렬되어 있지 않아도 사용이 가능하지만 데이터의 양이 많아질수록 비효율적일 수 있다.

각각 7과 13을 탐색

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // 찾은 경우 인덱스 반환
        }
    }
    return -1; // 찾지 못한 경우 -1 반환
}

---

2. 이진 탐색(Binary Search)

: 정렬된 데이터 집합에서 중간값과 목표 값을 비교하여 탐색 범위를 절반으로 줄여가는 방식이다. 데이터가 정렬되어 있어야 하며, 매우 효율적임!

각각 7과 13을 탐색

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // 찾은 경우 인덱스 반환
        }
    }
    return -1; // 찾지 못한 경우 -1 반환
}

---

3. 트리 탐색 : 전위 순회(Preorder Traversal)

: 전위 순회는 루트 노드를 먼저 방문한 후, 왼쪽 서브트리, 그리고 오른쪽 서브트리를 방문하는 순서다.

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

// 노드 구조체 정의
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 새로운 노드 생성
struct Node* createNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 전위 순회
void preorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    printf("%d ", node->data);  // 루트 방문
    preorderTraversal(node->left);  // 왼쪽 서브트리 방문
    preorderTraversal(node->right);  // 오른쪽 서브트리 방문
}

---

4. 트리 탐색 : 중위 순회(Inorder Traversal)

: 중위 순회는 왼쪽 서브트리를 먼저 방문한 후, 루트 노드를 방문하고, 마지막으로 오른쪽 서브트리를 방문하는 순서다.

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

// 노드 구조체 정의
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 새로운 노드 생성
struct Node* createNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 중위 순회
void inorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    inorderTraversal(node->left);  // 왼쪽 서브트리 방문
    printf("%d ", node->data);  // 루트 방문
    inorderTraversal(node->right);  // 오른쪽 서브트리 방문
}

---

5. 트리 탐색 : 후위 순회(Postorder Traversal)

: 후위 순회는 왼쪽 서브트리를 먼저 방문한 후, 오른쪽 서브트리, 그리고 루트 노드를 마지막에 방문하는 순서이다.

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

// 노드 구조체 정의
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 새로운 노드 생성
struct Node* createNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 후위 순회
void postorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    postorderTraversal(node->left);  // 왼쪽 서브트리 방문
    postorderTraversal(node->right);  // 오른쪽 서브트리 방문
    printf("%d ", node->data);  // 루트 방문
}