자료 구조 (2과목)

2과목 시작

자료 구조의 정의

• 자료 구조는 효율적인 프로그램 생산을 위해 가장 먼저 고려되는 저장 공간의 효율성과 실행시간의 신속성을 분석해야 하는데 있어 중요한 역할을 한다.
• 일련의 자료들을 조직화하고 구조화하는 것
• 어떠한 자료 구조에서도 필요한 연산들을 모두 처리할 수 있다.

---

자료 구조의 분류

• 자료 구조는 선형과 비선형으로 나뉜다.
• 선형은 일정 순서에 의해 나열된 자료 구조를 뜻한다.
• 선형 자료 구조는 다음과 같다.
  • 배열(Array)
  • 선형 리스트(Linear List)
    • 연속 리스트(Contiguous List)
    • 연결 리스트(Linked List)
  • 스택(Stack)
  • 큐(Queue)
  • 데크(Deque)
• 비선형 자료 구조는 다음과 같다.
  • 트리(Tree)
  • 그래프(Graph)

---

배열(Array)

• 정적인 자료 구조이다.
• 반복적인 데이터 처리 작업에 적합한 구조이다.
• 첨자를 이용하여 데이터에 접근한다.
• 사용한 첨자의 개수에 따라 n차원 배열이라고 불린다.

---

선형 리스트(Linear List)

• 연속 리스트(Contiguous List)
  • 기억장소 이용 효율은 1로 가장 좋다.
  • 연속적으로 기억장소에 저장되는 자료구조이다.
  • 중간에 삽입, 삭제 시 중간부터 이후 자료들 전체의 이동이 필요하다.
• 연결 리스트(Linked List)
  • 노드의 삽입과 삭제가 용이하다.
  • 기억 공간이 연속적으로 놓이지 않는다.
  • 연결을 위한 포인터와 자료가 연결되어 있는 구조이다.
  • 포인터를 찾아서 검색해야하기 때문에 접근 속도가 느린편이다.

---

스택(Stack)

• 리스트의 한쪽 끝으로만 자료의 삽입과 삭제가 이루어지는 자료 구조
• 스택은 서브루틴 호출, 재귀 호출, 후위 표기법 등 왔던 길을 되돌아 가는 경우에 사용된다.
• 스택이 모두 꽉 차있는 상태에서 데이터가 삽입되면 오버플로(Overflow)가 발생, 삭제할 데이터가 없는 상태에서 삭제를 하면 언더플로(Underflow)가 발생한다.
• TOP과 Bottom으로 가장 마지막 삽입된 자료의 위치가 TOP, 먼저 들어간 자료의 위치가 Bottom이다.
• FIFO(First in First Out)와 LIFO(Last In First Out) 중 LIFO를 채택하였다.

---

큐(Queue)

• 스택과 반대로 FIFO를 선택한 자료구조이다.(선입선출이라고 한다.)
• 리스트의 한쪽에서는 삽입, 반대쪽에서는 삭제가 이루어진다.
• 가장 먼저 들어간 자료의 위치를 Front 포인터, 마지막은 Rear 포인터로 각각 앞글자를 따서 F, R로 표기하기도 한다.
• 큐는 운영체제의 작업 스케쥴링에 사용된다.

---

그래프(Graph)

• 그래프 G(Graph)는 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어진다.
• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.
• 통신망(Network), 교통망 등에 응용된다.
• 트리(Tree)는 사이클이 없는 그래프이다.
• 무방향 그래프에서 최대 간선의 수는 V(V-1)/2이다.
• 방향 그래프에서 최대 간선의 수는 V(V-1)이다.

---