정보처리기사 : 자료구조

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

2. 배열 (Array)
- 일련의 동일한 자료형을 가진 데이터를 메모리 상에 연속적으로 저장한 자료구조
- 인덱스를 이용하여 원하는 데이터에 접근
- 빠른 검색 속도, 삽입/삭제가 어려워 메모리 낭비가 발생할 수 있음

3. 연속 리스트 
- 연속되는 기억장소에 저장되는 자료 구조
- 중간에 데이터가 삽입되려면 연속된 빈 공간이 있어야 함
- 삽입 삭제 시 자료의 이동 필요

4. 연결 리스트
- 자료들을 임의의 기억 공간에 기억 시키고 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킨 자료 구조
- 각각의 노드가 데이터와 다음 노드의 주소를 가리키는 포인터로 이루어짐
- 삽입/삭제가 용이, 접근 속도가 느림, 연결이 끊어지면 다음 노드 찾는 것이 어려움

5. 스택 
- 후입선출 구조
- 삽입과 삭제가 한쪽에서만 이루어지며, 최근에 삽입된 데이터가 먼저 삭제
- 저장할 공간이 없는데 삽입되면 오버플로, 삭제할 데이터가 없는데 삭제하면 언더플로 발생

6. 큐
- 선입선출 구조
- 삽입과 삭제가 서로 다른 쪽에서 이뤄짐, 가장 먼저 삽입된 데이터가 가장 먼저 삭제

7. 그래프 
- 정점과 간선의 두 집합으로 이루어진 자료 구조
- 사이클이 없는 그래프를 트리라고 한다. 

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