C 자료구조와 알고리즘 구현

자료구조와 알고리즘 구현

1. 연결 리스트 (Linked List)

연결 리스트는 데이터를 노드 단위로 저장하고, 각 노드는 다음 노드의 주소를 가리키는 구조입니다. 배열과 달리 크기가 유동적이며, 삽입 및 삭제가 빠르다는 특징이 있습니다. 특히 중간에 데이터를 추가하거나 제거할 때 배열에 비해 효율적입니다. 연결 리스트의 종류에는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있습니다.

단일 연결 리스트에서는 각 노드가 다음 노드의 주소만 알고 있어 한 방향으로만 탐색이 가능합니다. 반면 이중 연결 리스트는 이전 노드와 다음 노드를 모두 가리켜 양방향 탐색이 가능합니다. 원형 연결 리스트는 마지막 노드가 다시 첫 번째 노드를 가리켜 순환 구조를 만듭니다.

연결 리스트 기본 구현

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

struct Node {
    int data;
    struct Node* next;
};

void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    printList(head);

    return 0;
}
  

2. 스택 (Stack)과 큐 (Queue)

스택은 후입선출(LIFO, Last In First Out) 방식으로 데이터를 처리하는 자료구조로, 가장 마지막에 삽입된 데이터가 가장 먼저 제거됩니다. 반면 큐는 선입선출(FIFO, First In First Out) 방식으로, 가장 먼저 삽입된 데이터가 가장 먼저 제거됩니다. 스택은 함수 호출, 괄호 검사, 뒤집기 등에 활용되고, 큐는 작업 대기열, BFS 탐색 등에 자주 사용됩니다.

스택 구현

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

#define MAX 5
int stack[MAX];
int top = -1;

int isFull() {
    return top == MAX - 1;
}

int isEmpty() {
    return top == -1;
}

void push(int value) {
    if (isFull()) {
        printf("스택이 가득 찼습니다.\n");
    } else {
        stack[++top] = value;
        printf("%d가 스택에 추가되었습니다.\n", value);
    }
}

int pop() {
    if (isEmpty()) {
        printf("스택이 비었습니다.\n");
        return -1;
    } else {
        return stack[top--];
    }
}

int main() {
    push(10);
    push(20);
    push(30);
    printf("pop: %d\n", pop());
    push(40);
    return 0;
}
  

큐 구현

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

#define MAX 5
int queue[MAX];
int front = -1, rear = -1;

int isFull() {
    return rear == MAX - 1;
}

int isEmpty() {
    return front == -1 || front > rear;
}

void enqueue(int value) {
    if (isFull()) {
        printf("큐가 가득 찼습니다.\n");
    } else {
        if (front == -1) front = 0;
        queue[++rear] = value;
        printf("%d가 큐에 추가되었습니다.\n", value);
    }
}

int dequeue() {
    if (isEmpty()) {
        printf("큐가 비었습니다.\n");
        return -1;
    } else {
        return queue[front++];
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("dequeue: %d\n", dequeue());
    enqueue(40);
    return 0;
}
  

3. 트리 (Tree)

트리는 계층적 자료구조로, 루트 노드에서 시작해 자식 노드로 확장됩니다. 트리는 검색, 정렬, 계층적 데이터 표현에 효과적입니다. 종류로는 이진트리, 이진 탐색 트리(BST), AVL 트리, 힙 등이 있습니다. 이진 탐색 트리는 왼쪽 자식 노드는 부모보다 작은 값을, 오른쪽 자식 노드는 큰 값을 가집니다. 이를 통해 탐색을 빠르게 수행할 수 있습니다.

이진트리 구현

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node* root = (struct Node*)malloc(sizeof(struct Node));
    root->data = 1;
    root->left = (struct Node*)malloc(sizeof(struct Node));
    root->right = (struct Node*)malloc(sizeof(struct Node));
    
    root->left->data = 2;
    root->right->data = 3;
    
    root->left->left = NULL;
    root->left->right = NULL;
    root->right->left = NULL;
    root->right->right = NULL;

    inorder(root);
    return 0;
}
  

4. 정렬 알고리즘

정렬 알고리즘은 데이터를 특정 순서대로 배열하는 방법입니다. 기본 정렬 알고리즘으로는 버블 정렬, 선택 정렬, 삽입 정렬 등이 있고, 효율적인 정렬 알고리즘으로는 퀵 정렬, 병합 정렬, 힙 정렬 등이 있습니다. 정렬 알고리즘을 선택할 때는 데이터의 크기, 이미 정렬된 정도, 메모리 제약 등을 고려해야 합니다.

버블 정렬

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);

    printf("정렬된 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}
  

5. 탐색 알고리즘

탐색 알고리즘은 자료구조 내에서 원하는 값을 찾는 방법입니다. 대표적인 탐색 알고리즘인 이진 탐색은 정렬된 배열에서 빠르게 값을 찾을 수 있으며, 시간 복잡도가 O(log n)으로 매우 효율적입니다. 반면 선형 탐색은 정렬 여부와 관계없이 처음부터 순차적으로 찾으므로 시간 복잡도가 O(n)입니다.

이진 탐색

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result != -1) {
        printf("찾은 인덱스: %d\n", result);
    } else {
        printf("요소를 찾을 수 없습니다.\n");
    }
    return 0;
}
  

6. 재귀, 백트래킹, 다이내믹 프로그래밍

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 문제를 작은 단위로 나누어 해결합니다. 재귀를 적절히 사용하면 코드가 간결해지지만, 무한 재귀에 빠지지 않도록 종료 조건이 필수입니다. 백트래킹은 가능한 해를 찾을 때 조건에 맞지 않으면 이전 상태로 되돌아가 다른 경로를 탐색하는 방법입니다. 다이내믹 프로그래밍은 중복 계산을 줄이기 위해 이전에 계산한 결과를 저장해 효율성을 높이는 기법입니다.

재귀 예제 - 팩토리얼 계산

#include <stdio.h>

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    int n = 5;
    printf("팩토리얼: %d\n", factorial(n));
    return 0;
}
  

백트래킹 예제 - 8 퀸 문제

8 퀸 문제는 8 ×8 체스판 위에 8개의 퀸이 서로 공격하지 못하게 배치하는 문제입니다. 백트래킹을 이용해 한 줄씩 퀸을 놓으며 공격 불가능한 위치를 찾아 재귀적으로 해결합니다. 조건에 맞지 않으면 되돌아가 다른 위치를 탐색합니다.

#include <stdio.h&gt>
#include <stdbool.h>

#define N 8
int board[N];

bool isSafe(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col || abs(board[i] - col) == row - i)
            return false;
    }
    return true;
}

void printSolution() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i] == j) printf("Q ");
            else printf(". ");
        }
        printf("\n");
    }
    printf("\n");
}

void solve(int row) {
    if (row == N) {
        printSolution();
        return;
    }
    for (int col = 0; col < N; col++) {
        if (isSafe(row, col)) {
            board[row] = col;
            solve(row + 1);
        }
    }
}

int main() {
    solve(0);
    return 0;
}
  

다이내믹 프로그래밍 예제 - 피보나치수열

#include <stdio.h>

int fib(int n, int memo[]) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 10;
    int memo[11];
    for (int i = 0; i <= n; i++) memo[i] = -1;
    
    printf("피보나치 수열 %d번째 수: %d\n", n, fib(n, memo));
    return 0;
}