시나공 정보처리기사 실기 - 자료구조

자료구조

- 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리방법 등을 연구 분석하는 것

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

 

● 배열

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

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

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

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

 

● 연속 리스트

- 배열과 같이 기억장소에 저장되는 자료구조

- 중간에 데이터를 삽입하기 위해서느 연속된 빈 공간이 있어야함

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

 

● 연결 리스트

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

- 연결을 위한 링크(포인터) 부분이 필요 → 기억 공간의 이용 효율이 좋지 않음

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

 

● 스택

- 리스트의 한쪽 끝으로만 자료의 삽입(Push), 삭제(Pop) 작업이 이루어지는 자료구조

- 후입선출(LIFO) 

- 포화상태에서 데이터가 삽입되면 오버플로(Overflow) 발생

- 공백상태에서 데이터를 삭제하면 언더플로(Underflow) 발생

 

● 큐

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

- 선입선출(FIFO)

- 시작(Front)에서 삭제, 끝(Rear)에서 삽입이 이루어진다. 

- Deque : 큐의 시작과 끝에서 삽입, 삭제가 모두 이루어지는 자료구조

 

● 그래프

- 정점(Vertex)와 간선(Edge)의 두 집합으로 이루어지는 자료구조

- 트리 : 사이클이 없는 그래프

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

 

● 방향/무방향 그래프의 최대 간선 수 (n이 정점의 개수일 때)

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

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

 

● 트리 

- 정점(노드), 선분(가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태

- 노드 : 하나의 기억공간

- 근노드(Root node) : 트리구조에서 최고 조상 노드. 하나의 트리에 하나만 존재한다. 

- 링크 : 노드와 노드를 연결하는 선

- 차수(디그리) : 한 노드에 뻗은 가지의 수

- 단말노드(잎노드) : 자식이 없는 노드

- 트리의 디그리 : 가장 높은 차수