탐색 - 10. 고급 탐색 기법 및 응용 (Advanced Search Techniques and Applications)

📌 10. 고급 탐색 기법 및 응용 (Advanced Search Techniques and Applications)

---

10.1 이진 검색 트리(BST, Binary Search Tree) 소개 및 탐색

🔹 이진 검색 트리(Binary Search Tree)란?

이진 검색 트리(BST)는 각 노드의 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리입니다.

💡 BST의 특징

1. 왼쪽 서브트리의 값 < 부모 노드 < 오른쪽 서브트리의 값
2. 탐색(Search), 삽입(Insert), 삭제(Delete) 연산이 평균적으로 O(log n)의 시간 복잡도를 가짐
3. 정렬된 데이터를 빠르게 검색할 수 있음
4. 균형이 맞지 않으면(한쪽으로 치우친 경우) 성능이 O(n)까지 감소할 수 있음 → AVL 트리, Red-Black 트리 같은 균형 트리 사용

---

🔍 실습: 이진 검색 트리 구현 및 탐색 연산

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

// 이진 검색 트리 노드 구조체
typedef struct Node {
    int key;
    struct Node *left, *right;
} Node;

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

// BST 삽입 함수
Node* insert(Node* root, int key) {
    if (root == NULL) return createNode(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;
}

// BST 탐색 함수
Node* search(Node* root, int key) {
    if (root == NULL || root->key == key) return root;
    if (key < root->key) return search(root->left, key);
    return search(root->right, key);
}

// 최솟값 노드 찾기
Node* findMin(Node* root) {
    while (root->left != NULL) root = root->left;
    return root;
}

// BST 삭제 함수
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;
    
    if (key < root->key) root->left = deleteNode(root->left, key);
    else if (key > root->key) root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        Node* temp = findMin(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// 중위 순회 (오름차순 출력)
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("이진 검색 트리 (오름차순): ");
    inorder(root);
    printf("\n");

    printf("삭제 후 (70 삭제): ");
    root = deleteNode(root, 70);
    inorder(root);
    printf("\n");

    return 0;
}

📌 실행 결과

이진 검색 트리 (오름차순): 20 30 40 50 60 70 80
삭제 후 (70 삭제): 20 30 40 50 60 80

✔ 이진 검색 트리에서 삽입, 삭제, 탐색이 잘 동작!

---

10.2 A 탐색 알고리즘 개요 및 응용*

🔹 A 탐색 알고리즘이란?*

A* 탐색 알고리즘은 최단 경로를 찾기 위한 휴리스틱(heuristic) 기반 탐색 알고리즘입니다.

💡 A 알고리즘의 원리*

1. f(n) = g(n) + h(n)
   • g(n): 시작점에서 현재 노드까지의 비용
   • h(n): 현재 노드에서 목표까지의 추정 비용 (휴리스틱)
2. 우선순위 큐(최소 힙) 활용하여 가장 비용이 작은 경로 탐색
3. 미로 찾기, 게임 개발(경로 탐색), 로봇 경로 최적화 등에 사용됨

✔ 다익스트라(Dijkstra)와의 차이점

• 다익스트라는 모든 경로를 고려하는 반면,
• A*는 휴리스틱을 사용하여 유망한 경로를 우선 탐색 → 더 빠름

---

🔍 실습: A 알고리즘을 이용한 간단한 길 찾기*

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

#define N 5

// 방향 벡터 (상, 하, 좌, 우)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 노드 구조체
typedef struct {
    int x, y;
    int g, h, f;
} Node;

// 우선순위 큐 (간단한 버블 정렬 사용)
Node openList[N * N];
int openSize = 0;

void push(Node node) {
    openList[openSize++] = node;
    for (int i = openSize - 1; i > 0; i--) {
        if (openList[i].f < openList[i - 1].f) {
            Node temp = openList[i];
            openList[i] = openList[i - 1];
            openList[i - 1] = temp;
        }
    }
}

Node pop() {
    return openList[--openSize];
}

// 휴리스틱 계산 (맨해튼 거리)
int heuristic(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// A* 알고리즘
int Astar(int startX, int startY, int endX, int endY) {
    push((Node){startX, startY, 0, heuristic(startX, startY, endX, endY), 0});
    
    while (openSize > 0) {
        Node current = pop();

        if (current.x == endX && current.y == endY) return 1;

        for (int i = 0; i < 4; i++) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                int g = current.g + 1;
                int h = heuristic(nx, ny, endX, endY);
                push((Node){nx, ny, g, h, g + h});
            }
        }
    }

    return 0;
}

int main() {
    if (Astar(0, 0, 4, 4)) {
        printf("최단 경로 찾기 성공!\n");
    } else {
        printf("경로를 찾을 수 없습니다.\n");
    }
    return 0;
}

📌 실행 결과

최단 경로 찾기 성공!

✔ A 알고리즘을 이용한 경로 탐색 성공!*

---

📌 마무리 및 정리

• 이진 검색 트리(BST): 이진 탐색을 활용한 트리 구조, 탐색/삽입/삭제 O(log n)
• A 알고리즘*: 다익스트라 + 휴리스틱 기반 탐색, 경로 최적화에 활용
• 실습: BST 탐색 연산 구현, A* 알고리즘을 활용한 길 찾기