자료 구조

자료 구조 개요 및 핵심 정리

---

1. 자료 구조란?

• 정의: 자료를 기억장치 공간에 저장하고, 자료 간의 관계 및 처리 방법을 연구·분석하는 학문.
• 목적:
  1. 데이터를 효율적으로 관리.
  2. 탐색 시간 단축.
  3. 저장 공간 효율성.

---

2. 자료 구조의 분류

1. 선형 구조: 순서가 존재.
   • 예) 배열(Array), 스택(Stack), 큐(Queue), 데크(Deque), 리스트(List).
2. 비선형 구조: 순서가 존재하지 않음.
   • 예) 트리(Tree), 그래프(Graph).

---

3. 선형 구조

3.1 배열 (Array)

• 특징:
  • 같은 자료형의 데이터가 연속적으로 저장.
  • 순차적으로 탐색 가능.
• 장점:
  • 고정된 크기로 관리(정적).
  • 탐색 속도가 빠름 (첨자 활용).
• 단점:
  • 크기 변경 불가능.
  • 메모리 낭비가 발생 가능.
  • 중간 데이터 삽입·삭제 시 모든 데이터를 이동해야 함.

3.2 연속 리스트 (Sequential List)

• 배열과 유사하지만, 데이터 삽입·삭제를 지원.
• 삽입·삭제 시 연속적 이동이 필요.

3.3 연결 리스트 (Linked List)

• 특징:
  • 각 데이터가 노드(Node) 형태로 저장.
  • 노드는 데이터(Data)와 링크(Link)로 구성.
  • 데이터가 비연속적으로 저장되며, 링크를 통해 연결.
• 장점:
  • 크기 변경 가능.
  • 중간 데이터 삽입·삭제가 배열보다 효율적.
• 단점:
  • 메모리 사용량 증가 (링크 저장 공간 필요).
  • 탐색 속도가 느림 (순차 접근).

3.4 스택 (Stack)

• 특징:
  • 데이터 삽입과 삭제가 한쪽 끝에서만 이루어짐.
  • 후입선출 (LIFO): 마지막에 삽입된 데이터가 가장 먼저 삭제.
• 주요 연산:
  • Push: 데이터 삽입.
  • Pop: 데이터 삭제.
  • Top: 마지막 데이터 조회.
• 오류:
  • Overflow: 스택이 가득 찼을 때 삽입 시도.
  • Underflow: 스택이 비었을 때 삭제 시도.

3.5 큐 (Queue)

• 특징:
  • 선입선출 (FIFO): 먼저 들어간 데이터가 먼저 삭제.
  • 삽입은 Rear(뒤쪽), 삭제는 Front(앞쪽)에서 이루어짐.
• 주요 연산:
  • Enqueue: 데이터 삽입.
  • Dequeue: 데이터 삭제.

3.6 데크 (Deque)

• 특징:
  • 양쪽에서 삽입과 삭제가 가능.
  • 스택과 큐의 혼합형.

---

4. 비선형 구조

4.1 트리 (Tree)

• 특징:
  • 계층적 구조를 가진 자료구조.
  • 사이클(Cycle)이 없는 방향성 그래프.
  • 루트(Root) 노드를 중심으로 여러 자식 노드가 존재.

4.2 그래프 (Graph)

• 정의:
  • 노드(Node, 정점)와 간선(Edge)으로 구성.
• 특징:
  • 방향성 그래프: 간선에 방향이 존재.
  • 무방향 그래프: 간선에 방향이 없음.
• 최대 간선 수 계산:
  • 방향성 그래프: ( N(N-1) )
  • 무방향 그래프: ( \frac{N(N-1)}{2} )

---

5. 자료 구조 활용 예

자료 구조	활용 예시
배열 (Array)	성적 관리, 행렬 연산
스택 (Stack)	함수 호출, 괄호 검사
큐 (Queue)	프로세스 스케줄링, 프린터 대기열
데크 (Deque)	양방향 데이터 처리
트리 (Tree)	디렉토리 구조, 게임 트리
그래프 (Graph)	네트워크, 최단 경로 탐색

---

6. 요약 및 정리

1. 선형 구조: 데이터가 순서대로 저장되고 처리.
   • 배열, 스택, 큐, 데크, 리스트.
2. 비선형 구조: 데이터 간의 관계가 계층적이거나 복잡.
   • 트리, 그래프.
3. 자료 구조의 선택은 문제 특성과 효율성에 따라 결정.

자료 구조의 이해는 알고리즘 설계와 데이터 관리의 기본입니다. 각 구조의 장단점과 활용 사례를 잘 숙지하세요!