정렬과 탐색 알고리즘 완벽 가이드: 코드와 함께 배우는 기본 개념

---

트리(Tree)

트리 기본 개념

• 레벨(Level): 트리의 각 층.
• 높이(Height): 루트에서 가장 아래 단말 노드까지의 최대 거리.
• 차수(Degree): 각 노드의 자식 노드 개수.
• 형제 노드(Sibling): 동일 부모를 가지는 노드.
• 단말 노드(Leaf): 자식 노드가 없는 노드.

이진 트리(Binary Tree)

• 각 노드가 최대 두 개의 자식을 가짐.
• 노드 수:
  • 최소: 높이 hh일 때 hh개의 노드.
  • 최대: 2h−12^h - 1개의 노드.
• 간선 수: 노드 수 - 1.
• 노드 인덱스 관계:
  • 부모 인덱스: ⌊i/2⌋\lfloor i/2 \rfloor
  • 왼쪽 자식: 2i2i
  • 오른쪽 자식: 2i+12i + 1

순회 방식

1. 전위 순회 (Pre-order): VLR (방문 → 왼쪽 → 오른쪽)
2. 중위 순회 (In-order): LVR (왼쪽 → 방문 → 오른쪽)
3. 후위 순회 (Post-order): LRV (왼쪽 → 오른쪽 → 방문)

// 후위 순회
void postorder(TreeNode *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("[%d]", root->data);
    }
}

---

우선순위 큐와 히프

히프(Heap)

• 완전 이진 트리로 구현.
• 부모 노드의 값이 항상 자식 노드 값보다 큼(최대 히프) 또는 작음(최소 히프).

히프 정렬

void heap_sort(element a[], int n) {
    HeapType h;
    h = create();
    init(h);
    for (int i = 0; i < n; i++) {
        insert_max_heap(&h, a[i]);
    }
    for (int i = (n - 1); i >= 0; i--) {
        a[i] = delete_max_heap(&h);
    }
    free(h);
}

---

그래프(Graph)

기본 개념

• 정점(Vertex): 그래프의 각 점.
• 간선(Edge): 정점 간의 연결.
• 인접 행렬(Adjacency Matrix): 정점 간 연결 정보를 행렬로 표현.
• 인접 리스트(Adjacency List): 연결된 정점을 리스트로 표현.

탐색 알고리즘

1. 깊이 우선 탐색(DFS)
   • 재귀로 구현.
   • 방문한 정점의 자식을 먼저 탐색.

   void dfs_mat(GraphType *g, int v) {
       visited[v] = TRUE;
       printf("정점 %d -> ", v);
       for (int w = 0; w < g->n; w++) {
           if (g->adj_mat[v][w] && !visited[w]) {
               dfs_mat(g, w);
           }
       }
   }
   

2. 너비 우선 탐색(BFS)
   • 큐로 구현.
   • 현재 정점의 모든 인접 정점을 방문 후, 자식 정점을 탐색.

   void bfs_mat(GraphType *g, int v) {
       QueueType q;
       queue_init(&q);
       visited[v] = TRUE;
       enqueue(&q, v);
       while (!is_empty(&q)) {
           v = dequeue(&q);
           printf("%d 방문 -> ", v);
           for (int w = 0; w < g->n; w++) {
               if (g->adj_mat[v][w] && !visited[w]) {
                   visited[w] = TRUE;
                   enqueue(&q, w);
               }
           }
       }
   }
   

---

정렬(Sorting)

1. 삽입 정렬: 데이터를 하나씩 정렬된 영역에 삽입.

   void insertion_sort(int list[], int n) {
       for (int i = 1; i < n; i++) {
           int key = list[i];
           int j = i - 1;
           while (j >= 0 && list[j] > key) {
               list[j + 1] = list[j];
               j--;
           }
           list[j + 1] = key;
       }
   }
   

2. 퀵 정렬: 피벗을 기준으로 데이터를 분할하며 정렬.
3. 합병 정렬: 데이터를 반씩 나누고 합치며 정렬.

---

탐색(Search)

1. 순차 탐색: 데이터를 처음부터 순서대로 탐색.
2. 이진 탐색: 데이터가 정렬되어 있을 때, 중간값을 기준으로 탐색 범위를 줄임.

   int search_binary2(int key, int low, int high) {
       while (low <= high) {
           int mid = (low + high) / 2;
           if (key == list[mid])
               return mid;
           else if (key < list[mid])
               high = mid - 1;
           else
               low = mid + 1;
       }
       return -1;
   }