1. 이진 트리 순회

순회 방법:

  • 전위 순회 (Preorder): 루트 방문 -> 왼쪽 자식 -> 오른쪽 자식
  • 중위 순회 (Inorder): 왼쪽 자식 -> 루트 방문 -> 오른쪽 자식
  • 후위 순회 (Postorder): 왼쪽 자식 -> 오른쪽 자식 -> 루트 방문
  • 레벨 순서 (Level Order): 루트부터 레벨별로 방문

순회 알고리즘:

void preOrder(treePointer ptr) {
    if (ptr != NULL) {
        visit(ptr);
        preOrder(ptr->leftChild);
        preOrder(ptr->rightChild);
    }
}

void inOrder(treePointer ptr) {
    if (ptr != NULL) {
        inOrder(ptr->leftChild);
        visit(ptr);
        inOrder(ptr->rightChild);
    }
}

void postOrder(treePointer ptr) {
    if (ptr != NULL) {
        postOrder(ptr->leftChild);
        postOrder(ptr->rightChild);
        visit(ptr);
    }
}


예제

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

// 이진 트리 노드 정의
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int traversal(TreeNode* root, int prevMax) {
    if (root == NULL) return 0;
    int GoodNode = root->val >= prevMax ? 1 : 0;
    int maxVal = GoodNode ? root->val : prevMax;
    int l = traversal(root->left, maxVal);
    int r = traversal(root->right, maxVal);
    return l + r + GoodNode;
}

int goodNodes(TreeNode* root) {
    if (root == NULL) return 0;
    return traversal(root, root->val);
}

int main() {
    TreeNode n1 = {1, NULL, NULL};
    TreeNode n4 = {4, NULL, NULL};
    TreeNode n3 = {3, &n1, &n4};
    int result = goodNodes(&n3);
    printf("Number of good nodes: %d\n", result);
    return 0;
}

2. 이진 검색 트리 (Binary Search Tree)

이진 검색 트리의 특성:

  • 각 노드는 (키, 값) 쌍을 가짐.
  • 노드 x의 왼쪽 서브트리의 모든 키는 x의 키보다 작음.
  • 노드 x의 오른쪽 서브트리의 모든 키는 x의 키보다 큼.

예제 문제:

  • 문제: 주어진 이진 트리가 이진 검색 트리인지 확인하라.
#include <stdio.h>
#include <stdlib.h>

// 이진 트리 노드 정의
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int isBSTNode(TreeNode* root, int min, int max) {
    if (root == NULL) return 1;
    if (root->val <= min || root->val >= max) return 0;
    return isBSTNode(root->left, min, root->val) && isBSTNode(root->right, root->val, max);
}

int isBST(TreeNode* root) {
    return isBSTNode(root, INT_MIN, INT_MAX);
}

int main() {
    TreeNode n1 = {1, NULL, NULL};
    TreeNode n4 = {4, NULL, NULL};
    TreeNode n3 = {3, &n1, &n4};
    int result = isBST(&n3);
    printf("Is BST: %d\n", result);
    return 0;
}

3. 힙 (우선순위 큐)

힙의 특성:

  • 요소의 모음.
  • 각 요소는 우선순위 또는 키를 가짐.
  • 지원하는 연산:
    • 비어있는지 확인 (Empty)
    • 크기 확인 (Size)
    • 요소 삽입 (push)
    • 최대 우선순위 요소 얻기 (top)
    • 최대 우선순위 요소 제거 (pop)

예제 문제: 더 맵게


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

#define MAX_ELEMENT 100

typedef struct {
    int heap[MAX_ELEMENT];
    int heap_size;
} heapType;

heapType *createHeap() {
    heapType *h = (heapType*)malloc(sizeof(heapType));
    if (h == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    h->heap_size = 0;
    return h;
}

int topHeap(heapType *h) {
    if (h->heap_size == 0) {
        fprintf(stderr, "Heap is empty\n");
        return -1;
    }
    return h->heap[0];
}

int popHeap(heapType *h) {
    if (h->heap_size == 0) {
        fprintf(stderr, "Heap is empty\n");
        return -1;
    }
    int min = h->heap[0];
    h->heap[0] = h->heap[--h->heap_size];
    int parent = 0;
    while (1) {
        int leftChild = 2 * parent + 1;
        int rightChild = 2 * parent + 2;
        int smallest = parent;
        if (leftChild < h->heap_size && h->heap[leftChild] < h->heap[smallest]) smallest = leftChild;
        if (rightChild < h->heap_size && h->heap[rightChild] < h->heap[smallest]) smallest = rightChild;
        if (smallest == parent) break;
        int temp = h->heap[parent];
        h->heap[parent] = h->heap[smallest];
        h->heap[smallest] = temp;
        parent = smallest;
    }
    return min;
}

void pushHeap(heapType *h, int item) {
    if (h->heap_size >= MAX_ELEMENT) {
        fprintf(stderr, "Heap is full\n");
        return;
    }
    int i = h->heap_size++;
    while (i && item < h->heap[(i - 1) / 2]) {
        h->heap[i] = h->heap[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    h->heap[i] = item;
}

int solution(int scoville[], int n, int k) {
    heapType *heap = createHeap();
    for (int i = 0; i < n; i++) pushHeap(heap, scoville[i]);
    int cnt = 0;
    while (topHeap(heap) < k && heap->heap_size > 1) {
        int a = popHeap(heap);
        int b = popHeap(heap);
        pushHeap(heap, a + b * 2);
        cnt++;
    }
    if (topHeap(heap) < k) return -1;
    return cnt;
}

int main() {
    int scoville[] = {1, 2, 3, 9, 10, 12};
    int n = sizeof(scoville) / sizeof(scoville[0]);
    int k = 7;
    int result = solution(scoville, n, k);
    printf("Minimum number of operations: %d\n", result);
    return 0;
}



코드 내용은 시험에 나오지 않음