[2020 정보처리기사 필기] 2.1.34 자료구조

# 필기 참고: 시나공 정보처리기사 2. 소프트웨어 개발 >1.데이터 입.출력 구현

 

1. 자료구조의 정의

- 목적: 저장공간의 효율성과 실행시간의 신속성

- 의미: 자료를 기억장치의 기억공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료의 관계, 처리방법 등

 

2. 자료구조 분류

- 선형구조: 배열, 선형 리스트(연속 리스트, 연결 리스트), 스택, 큐, 데크

- 비선형 구조: 트리, 그래프

 

3. 배열

- 동일한 자료형의 데이터들이 같은 크기로 나열. 

- 정적이다. -> 메모리 추가 어렵고, 삭제시 저장되어있던게 빈공간 되니까 메모리 낭비

- index 이용하여 데이터 접근

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

- 데이터마다 동일한 이름의 변수 사용-> 처리 간편

-

4. 선형 리스트(Linear List)

- 일정한 순서에 의해 나열된 자료구조

- 연속리스트

   - 배열을 이용함. 배열 같이 연속되는 기억장소에 저장되는 자료 구조

   - 기억장소를 연속적으로 배정받음-> 효율: 밀도가 1로서 좋다

   - 중간에 데이터 삽입시 연속된 빈 공간 필요. 삽입 삭제시 자료의 이동 필요

- 연결리스트

   - 포인터 이용-> 서로 연결됨

   - 삽입, 삭제 용이

   - 메모리가 연속적으로 안놓여도 저장 가능

   - 연결을 위한 포인터 필요 -> 메모리 이용 효율 좋지 않음.

   - 접근 속도 느림. <- 포인터 찾는 시간 필요하니까!

   - 중간 노드 연결 끊어지면, 다음 노드 찾기 어렵다.

 

5. 스택

- LIFO 구조

- 오버플로우: 메모리 꽉 차있는데 데이터 삽입 시 발생 

  언더플로우: 삭제할 데이터 없는데 데이터 삭제시 발생

- top : 가장 마지막으로 삽입된 자료가 기억된 위치

  bottom: 스택의 가장 밑바닥

 

6. 큐

- 리스트 한쪽: 삽입, 반대쪽 : 삭제

- FIFO 구조

- 시작과 끝을 표시하는 두개의 포인터 존재

   - Front:  가장 먼저 삽입된 자료의 메모리 가리키는 포인터

   - Rear: 가장 마지막에 삽입된 자료가 위치한 메모리 가리키는 포인터

- 운영체제의 작업 스케줄링에 이용됨.

 

7.  트리

- Node와 Branch 사용해 '사이클 이루지 않도록' 구성한 그래프의 특수한 형태

- 노드: 하나의 기억공간

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

-

트리 구조

- 차수(degree): 각 노드에서 뻗어 나온 가지수

- terminal node = leaf node

-트리의 차수: 노드들의 차수 중 가장 많은 수