[정보처리기사] - 자료 구조

자료 구조

- 자료 구조는 자료를 기억장치의 공간 내에 저장하는 방법을 말한다.

- 저장 공간의 효율성과 실행시간의 단축을 위해 사용한다.

 

선형구조

- 배열

- 선형 리스트 

    - 연속 리스트

    - 연결 리스트

- 스택

- 큐

- 데크

 

비선형구조

- 트리

- 그래프

 

배열 ( Array )

- 크기와 타입이 동일한 자료들이 순서대로 나열된 자료의 집합

- 반복적인 데이터 처리 작업에 적합한 구조

- 정적인 자료구조로, 기억장소의 추가가 어렵다

- 데이터 삭제 시 기억장소가 빈 공간으로 남아있어 메모리의 낭비가 발생

 

연속 리스트 ( Contiguous List )

- 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.

- 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.

- 삽입, 삭제 시 자료의 이동이 필요

 

연결 리스트 ( Linked List )

- 연결 리스트는 자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조

- 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억 공간의 이용 효율이 좋지 않다.

- 접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어렵다.

 

스택 ( Stack )

- 스택은 리스트의 한쪽 끝으로만 데이터의 삽입, 삭제 작업이 이루어지는 자료 구조이다.

- 후입선출 (LIFO : Last In First Out) 방식으로 자료를 처리함

- 저장할 기억 공간이 없는 상태에서 데이터가 삽입되면 오버플로(Overflow)가 발생

- 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생

 

큐 ( Qeueu )

- 큐는 리스트의 한쪽에서는 삽입 작업이, 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조이다.

- 선입선출(FIFO : First In First Out) 방식으로 처리한다.

- 시작을 표시하는 프런트(Front) 포인터와 끝을 표시하는 리어(Rear) 포인터가 있다.

 

그래프 ( Graph )

- 그래프는 정점과 간선의 두 집합으로 이루어지는 자료 구조이다.

- 사이클이 없는 그래프를 트리(Tree) 라고 한다.

- 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분됨.

- 방향 그래프의 최대 간선 수 : n(n-1)

- 무방향 그래프에서 최대 간선 수 : n(n-1) / 2

n은 정점의 개수이다.

 

트리 ( Tree )

- 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 한다.

- 근노드 : 트리의 맨 위 노드 A

- 디그리 : 각 노드에서 뻗어나온 가지의 수 ex) A=3, B=2, C=1

- 단말 노드 = 잎 노드 : 자식이 하나도 없는 노드, 즉 Degree가 0인 노드 ex) F, G, H, I, J, K

- 비단말 노드 : 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드

- 조상 노드 : 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들 ex) K의 조상 노드는 E, B, A

- 자식 노드 : 어떤 노드에 연결된 다음 레벨의 노드 ex) B의 자식 노드 : E, F

- 부모 노드 : 어떤 노드에 연결된 이전 레벨의 노드 ex) E, F 의 부모 노드 : B

- 형제 노드 : 동일한 부모를 갖는 노드 ex) K의 형제노드 : J

- Level : 근 노드의 Level을 1로 가정한 후 다음 자식 노드들은 Level + 1

- 깊이(Depth, Height) : Tree에서 노드가 가질 수 있는 최대의 Level

- 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수 ex) 위 트리의 디그리는 3이다.

 

이진 트리

- 이진 트리는 차수가 2 이하인 노드들로 구성된 트리이다.

 

트리의 운행법

- Preorder : Root -> Left -> Right 순으로 운행한다. 

- Inorder : Left -> Root -> Right 순으로 운행한다.

- Postorder : Left -> Right -> Root 순으로 운행한다.