자료 구조 정리

자료 구조의 분류

• 선형 구조 (Linear Structures)
  • 배열 (Array)
    • 동일한 데이터 타입의 요소들이 연속된 메모리 공간에 저장된 자료구조.
    • 예시: int arr[5] = {1, 2, 3, 4, 5};
  • 선형 리스트 (Linear List)
    • 연속 리스트 (Sequential List): 배열과 유사하지만, 크기를 동적으로 변경할 수 없음. 예시: int list[5] = {10, 20, 30, 40, 50};
    • 연결 리스트 (Linked List): 각 노드가 데이터와 다음 노드를 가리키는 포인터를 포함한 자료구조. 예시: 10 -> 20 -> 30 -> NULL
  • 스택 (Stack)
    • LIFO (Last In, First Out) 방식으로, 나중에 들어간 데이터가 먼저 나오는 구조. 예시: 웹 브라우저의 뒤로 가기 기능 (최근 페이지부터 먼저 나옴).
  • 큐 (Queue)
    • FIFO (First In, First Out) 방식으로, 먼저 들어간 데이터가 먼저 나오는 구조. 예시: 줄 서기(먼저 줄 선 사람이 먼저 처리됨).
  • 데크 (Deque)
    • Double-ended Queue로, 앞뒤 양쪽에서 삽입과 삭제가 가능한 구조. 예시: 양방향에서 출입이 가능한 대기열.

---

• 비선형 구조 (Non-linear Structures)
  • 트리 (Tree)
    • 계층적인 구조로, 루트 노드가 있고 여러 자식 노드들이 있는 자료구조. 예시: 조직도, 디렉토리 구조 (루트 디렉토리 → 서브 디렉토리 → 파일).
  • 그래프 (Graph)
    • 정점(노드)과 간선(엣지)으로 이루어진 자료구조로, 여러 노드들이 연결된 구조. 예시: 소셜 네트워크(사용자 간의 친구 관계), 도시 간의 도로망.

스택

• 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.
• 후입선출(LIFO: LAST IN FIRST OUT) 방식으로 자료를 처리한다.
• 저장할 기억 공간이 없는 상태에서 데이터가 삽입되면 오버플로(OVERFLOW)가 발생한다.
• 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(UNDERFLOW)가 발생한다.

방향/무방향 그래프의 최대 간선 수

• 방향 그래프의 최대 간선 수: n*(n-1)
• 무방향 그래프의 최대 간선 수: n*(n-1)/ 2

→ n은 정점의 개수

• 방향 그래프 (Directed Graph)
• • 정점이 4개(A, B, C, D)인 경우, 각 정점이 다른 모든 정점으로 향하는 방향 간선을 가질 수 있습니다.
  • 최대 간선 수: 4×(4−1)=12
  • 4×(4−1)=124 \times (4 - 1) = 12
  • 간선의 예시 (총 12개):
    • A → B, A → C, A → D
    • B → A, B → C, B → D
    • C → A, C → B, C → D
    • D → A, D → B, D → C
• 무방향 그래프 (Undirected Graph)
  • 정점이 4개(A, B, C, D)인 경우, 한 쌍의 정점이 양방향으로 연결되며 중복 없이 연결됩니다.
  • 최대 간선 수: 24×(4−1)=6
  • 4×(4−1)2=6\frac{4 \times (4 - 1)}{2} = 6
  • 간선의 예시 (총 6개):
    • A — B, A — C, A — D
    • B — C, B — D
    • C — D

트리 관련 용어

	  A
       /  |  \
     B    C    D
    / \   |   / \
   E   F  G  H   I
  / \     |      \
 J   K    L       M

• 노드 (Node)
  • 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것입니다.
• 예시
  • 위 트리에서 A, B, C, D, E, F, G, H, I, J, K, L, M 모두가 노드입니다.

---

• 근 노드 (Root Node)
  • 트리에서 가장 위에 위치한 노드입니다.
• 예시
• 위 트리에서 A는 근 노드입니다.

---

• 차수 (디그리, Degree)
  • 각 노드에서 뻗어나온 가지의 수입니다.
• 예시
  • A의 차수: 3 (B, C, D의 자식 노드가 있음)
  • B의 차수: 2 (E, F의 자식 노드가 있음)
  • 트리의 차수: 트리에서 차수가 가장 큰 노드인 A의 차수는 3입니다.

---

• 단말 노드 (Leaf Node/Terminal Node)
  • 자식 노드가 없는, 즉 차수가 0인 노드를 단말 노드라고 합니다.
• 예시
  • 위 트리에서 J, K, F, L, M은 단말 노드입니다.

---

• LEVEL (레벨)
  • 트리에서 루트 노드로부터의 깊이를 의미합니다. 루트 노드의 레벨은 0이며, 아래로 내려갈수록 레벨이 1씩 증가합니다.
  • 근 노드의 LEVEL을 1로 가정한후 어떤 LEVEL이 L이면 자식 노드는 L+1
• 예시
  • A: 레벨 0
  • B, C, D: 레벨 1
  • E, F, G, H, I: 레벨 2
  • J, K, L, M: 레벨 3

---

• 깊이 (Depth)
  • 트리에서 루트 노드에서 특정 노드까지의 거리를 깊이라고 합니다. 트리 전체의 깊이는 루트 노드에서 가장 깊숙이 있는 단말 노드의 레벨로 측정합니다.
• 예시
  • J의 깊이: 3 (A → B → E → J)
  • 트리의 깊이: 3 (가장 깊은 레벨에 있는 노드가 J, K, L, M이므로, 트리 전체 깊이는 3)

---

• 숲 (Forest)
  • 트리에서 루트 노드를 제거했을 때 남은 여러 개의 서브 트리를 숲이라고 합니다.
• 예시
  • 위 트리에서 A를 제거하면, 다음과 같은 3개의 서브 트리가 남습니다:

      B        C      D
    /   \        \   /   \
  E     F       G  H    I
 / \            |        \
J   K           L         M

이 3개의 서브 트리가 숲을 형성합니다.

---

• 트리의 디그리
  • 노드들의 디그리 중에서 가장 많은 수
• 예시
  • 노드 A가 3개의 디그리를 가지므로 위 트리의 디그리는 3이다.