[2023 정보처리기사] 2과목

1. 자료구조

: 프로그램에서 사용하기 위한 자료를 기억장치 공간에 저장하는 방법과 자료간의 관계.

1. 1. 자료구조의 분류

2. 비선형 구조(Non-Linear Structure)

2. 1. 트리 (Tree) ★★

: 정점(노드, Node)과 선분(가지, Branch)을 이용하여 사이클을 이루지 않도록 구성.

– 노드: 하나의 기억공간.

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

<출처: https://velog.io/@codenmh0822/비선형-자료구조-트리Tree>

노드(Node): 트리의 기본 요소: A, B, C, D, E, F, G, H, I, J
근 노드(Root): 트리의 최상위: A
디그리(차수, Degree): 각 노드에서 받은 가지 수: A=2, B=2, E=1
단말 노드(Terminal Node): 자식이 없는 노드: F, G
부모 노드(Parant Node): 어떤 노드에 연결된 이전 노드: H, I의 부모 노드=D
자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨 노드: D의 자식 노드=H, I
형제 노드(Brother Node): 동일한 부모를 갖는 노드: H의 형제 노드=I
트리의 디그리: 노드들의 디그리 중 가장 많은 수:2

2. 1. 1. 이진트리의 운행법(순회법, Traversal) ★★

* 이진트리: 디그리가 2 이하인 노드들로 구성된 트리

<출처: https://blog.naver.com/occidere/220899936160>

전위 운행(Preorder): Root -> Left -> Right
중위 운행(Inorder): Left -> Root -> Right
후위 운행(Postorder): Left -> Right -> Root

2. 2. 그래프(Graph)

2. 2. 1. 방향 그래프

– 정점을 연결하는 선에 방향이 있는 그래프

– 방향 그래프의 최대 간선 수 = N(N-1) *N:정점의 갯수

2. 2. 2. 무방향 그래프

– 정점을 연결하는 선에 방향이 없는 그래프

– 무방향 그래프의 최대 간선 수 = N(N-1)/2 *N:정점의 갯수

3. 선형 구조(Linear Structure)

3. 1. 배열(Array)

: 동일한 자료의 데이터들이 같은 크기로 나열되어 순서를 갖는 집합.

– 정적인 자료구조. 추가가 어려움. 데이터 삭제시 빈 공간으로 메모리 낭비 발생.

– 반복적인 데이터 처리 작업에 적합. 동일한 이름의 변수사용으로 데이터 처리가 간편.

3. 2. 선형 리스트(Linear List)

: 일정한 순서에 의해 나열된 구조

3. 2. 1. 연속 리스트(Contiguous List) *배열 이용

: 배열과 같이 연속되는 기억장소에 저장.

– 기억장소를 연속으로 배정하여 기억장소 이용 효율이 좋음.

– 중간에 데이터 삽입을 위해 연속된 빈 공간 필요. 삽입⋅삭제시 자료의 이동 필요.

3. 2. 2. 연결 리스트(Linked List) *포인터 이용

: 자료를 반드시 연속적으로 배열시키지 않고, 노드의 포인터 부분을 이용하여 서로 연결

*포인터: 다음 노드의 위치(주소)를 알려주는 데이터.

*노드: 자료를 저장하는 데이터 부분과 다음 노드를 가리키는 포인터(링크)로 구성.

– 노드의 삽입⋅삭제 작업이 용이.

– 연속적으로 놓여있지 않아도 저장 가능.

– 연결을 위한 링크(포인터)가 필요해, 기억공간 이용 효율이 좋지 않음.

– 포인터를 찾는 시간이 필요해, 접근속도가 느림.

3. 3. 스택(Stack) ★

: 리스트의 한쪽 끝으로만 자료의 삽입⋅삭제 작업이 이루어짐.

– 후입선출(LIFO, Last In First Out)방식

– 스택이 꽉 찼을 때 데이터 삽입시 오버플로우(Overflow)발생

– 데이터가 없을 때 삭제시 언더플로우(Underflow)발생.

*스택가드 : 메모리상에서 프로그램의 복귀주소와 변수 사이에 특정 값을 저장해 두었다가 그 값이 변경되었을 경우 오버플로우, 이후 프로그램 중지.

3. 4. 큐(Queue) ★

: 리스트의 한쪽 끝은 삽입, 다른 한쪽 끝은 삭제로 이루어진 구조.

– 선입 선출(FIFO, First In First Out)방식.

– 시작과 끝을 표시하는 2개의 포인터 필요.

– 운영체제의 작업 스케줄링에 사용.

3. 5. 데크(Deque)

: 리스트의 양쪽 끝에서 삽입⋅삭제가 이루어짐.

– 스택과 큐를 복합한 구조.

[2023 정보처리기사] 2과목 – 1. 자료구조