고급 알고리즘

1. A* 알고리즘 (A-Star Algorithm)

1.1 개념

A* 알고리즘은 최단 경로 탐색을 위한 휴리스틱 기반 탐색 알고리즘이다. 다익스트라 알고리즘과 유사하지만, 휴리스틱 함수를 사용하여 탐색 속도를 향상시킨다.

1.2 수식

A* 알고리즘에서는 평가 함수 ( f(n) )을 사용하여 최적의 경로를 찾는다.

여기서:

• ( g(n) ) : 시작 노드에서 현재 노드까지의 비용
• ( h(n) ) : 현재 노드에서 목표 노드까지의 휴리스틱 비용 (예: 맨해튼 거리, 유클리드 거리 등)

1.3 C 코드 예제

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

#define INF 1e9
#define N 5  // 노드 개수

// 유클리드 거리 휴리스틱 함수
double heuristic(int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
    // A* 알고리즘 구현 (간단한 예제)
    printf("A* 알고리즘 예제\n");
    return 0;
}

---

2. KMP 알고리즘 (Knuth-Morris-Pratt)

2.1 개념

KMP 알고리즘은 문자열 검색을 위한 효율적인 알고리즘으로, 불필요한 비교를 줄여 빠르게 검색을 수행한다.

2.2 수식

• 접두사-접미사 테이블 ( pi[i] )를 생성하여 패턴이 불일치할 경우, 이동할 위치를 결정한다.

2.3 C 코드 예제

#include <stdio.h>
#include <string.h>

void computeLPSArray(char *pattern, int M, int *lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMP(char *text, char *pattern) {
    int N = strlen(text);
    int M = strlen(pattern);
    int lps[M];
    computeLPSArray(pattern, M, lps);
    int i = 0, j = 0;
    while (i < N) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == M) {
            printf("패턴이 %d 위치에서 발견됨\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    KMP(text, pattern);
    return 0;
}

---

3. 트라이 (Trie) 알고리즘

3.1 개념

트라이(Trie)는 문자열 탐색을 위한 트리 자료구조로, 검색, 삽입, 삭제 연산이 빠르다.

3.2 C 코드 예제

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

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    int isEndOfWord;
} TrieNode;

TrieNode *createNode() {
    TrieNode *node = (TrieNode *)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL;
    return node;
}

void insert(TrieNode *root, const char *key) {
    TrieNode *node = root;
    for (int i = 0; key[i]; i++) {
        int index = key[i] - 'a';
        if (!node->children[index])
            node->children[index] = createNode();
        node = node->children[index];
    }
    node->isEndOfWord = 1;
}

int search(TrieNode *root, const char *key) {
    TrieNode *node = root;
    for (int i = 0; key[i]; i++) {
        int index = key[i] - 'a';
        if (!node->children[index])
            return 0;
        node = node->children[index];
    }
    return node->isEndOfWord;
}

int main() {
    TrieNode *root = createNode();
    insert(root, "hello");
    printf("hello 검색 결과: %d\n", search(root, "hello"));
    printf("world 검색 결과: %d\n", search(root, "world"));
    return 0;
}