[정보처리기사 필기] 자료 구조 (Data Structure)
¶ 자료 구조의 개념
- 자료 구조는 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조이다.
- 자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킨다.
¶ 자료 구조의 분류
| 구조 | 설명 | 종류 |
| 선형 구조 | 데이터를 연속적으로 연결한 자료 구조 | 리스트, 스택, 큐, 데크 |
| 비선형 구조 | 데이터를 비연속적으로 연결한 자료 구조 | 트리, 그래프 |
선형 구조
① 리스트(List)
▶ 리스트의 종류
| 종류 | 설명 |
| 선형 리스트 (Linear List) |
- 배열과 같이 연속되는 기억 장소에 저장되는 리스트 - 선형 리스트의 대표적인 구조로는 배열(Array) 등이 있음 - 가장 간편한 자료 구조이며, 접근 구조가 빠름 - 자료의 삽입, 삭제 시 기존 자료의 이동이 필요 |
| 연결 리스트 (Linked List) |
- 노드의 포인터 부분으로 서로 연결시킨 리스트 - 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분 - 노드의 삽입, 삭제가 선형 리스트와 달리 편리 - 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요 - 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림 |
선형 리스트는 연속되는 기억 장소, 연결 리스트는 포인터 연결
② 스택(Stack)
스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO(Last-In First-Out) 형식의 자료 구조이다.
- 한 방향으로만 PUSH와 POP을 이용하여 자료를 넣고 꺼낸다.
- TOP은 스택에서 가장 위에 있는 데이터로, 스택 포인터(Stack Pointer) 라고도 불린다.
▶ 스택 연산
| 연산 | 설명 |
| PUSH | 데이터를 차례대로 스택에 넣는 연산 |
| POP | 스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산 |
▶ 스택 응용 분야
| 분야 | 설명 |
| 인터럽트의 처리 | 현재 진행 중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행 중이던 명령어 위치를 스택에서 POP을 통해 받아옴 |
| 함수 호출 (재귀 호출 포함) |
함수를 호출 시 현재 진행 중인 명령어 주소를 스택에 저장 |
| 후위표현 연산 | Postfix 를 계산할 때 사용 |
| 깊이 우선 탐색 (DFS: Depth-Frist Search) |
깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾음 |
③ 큐(Queue)
큐는 한쪽 끝에서는 삽입 작업이 이뤄지고, 반대쪽 끝에서는 삭제 작업이 이루어지는 FIFO(First-In First-Out) 형식의 자료 구조이다.
- 한쪽에서는 ENGUEUE 연산을 이용하여 데이터를 넣고, 한쪽에서는 DEQUEUE 연산을 이용하여 데이터를 꺼낸다.
- 데이터가 꺼내는 쪽에서 가장 가까운 데이터를 Front라고 하고, 데이터를 넣는 쪽에서 가장 가까운 데이터를 Rear라고 한다.
▶ 큐 연산
| 연산 | 설명 |
| ENQUEUE | 데이터를 차례대로 넣는 연산 |
| DEQUEUE | 처음 저장된 데이터부터 하나씩 꺼내는 연산 |
④ 데크 (Deque: Double Ended Queue)
데크는 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조이다.
- 두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다.
- 데크를 이용한 스택과 큐의 구현이 가능하다.
▶ 데크 연산
| 연산 | 설명 |
| PUSH | 데이터를 차례대로 데크에 넣는 연산 |
| POP | 데크에서 Front와 Rear에 있는 데이터를 하나씩 꺼내는 연산 |
비선형 구조
① 트리
- 트리는 데이터들을 계층화시킨 자료 구조이다.
- 그래프의 특수한 형태로 노드와 선분(Branch)으로 되어 있고, 정점 사이에 사이클이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조이다.
- 인덱스를 조작하는 방법으로 가장 많이 사용하는 구조이다.
- 트리는 노드와 노드를 연결하는 링크로 구성된다.
- 배열과 달리 노드들이 포인터로 연결되어 노드의 상한선이 없다.
▶ 트리 용어
| 용어 | 설명 |
| 루트 노드 (Root Node) |
- 트리에서 부모가 없는 최상위 노드, 트리의 시작점 - (10) |
| 단말 노드 (Leaf Node) |
- 자식이 없는 노드, 트리의 가장 말단에 위치 - (3, 6, 19) |
| 레벨 (Level) |
- 루트 노드를 기준으로 특정 노드까지의 경로 길이 - 19의 레벨은 2 |
| 조상 노드 (Ancestor Node) |
- 특정 노드에서 루트에 이르는 경로상 모든 노드 - 3의 조상 노드는 (5, 10) |
| 자식 노드 (Child Node) |
- 특정 노드에 연결된 다음 레벨의 노드 - 5의 자식 노드는 (3, 6) |
| 부모 노드 (Parent Node) |
- 특정 노드에 연결된 이전 레벨의 노드 - 3의 부모 노드는 (5) |
| 형제 노드 (Sibling) |
- 같은 부모를 가진 노드 - 3의 형제 노드는 (6) |
| 깊이 (Depth) |
- 루트 노드에서 특정 노드에 도달하기 위한 간선의 수 - 트리의 깊이는 2 |
| 차수 (Degree) |
- 특정 노드에 연결된 자식 노드의 수 - 5의 차수는 2 |
▶ 트리 순회방법
| 방법 | 개념도 | 설명 |
| 전위 순회 (Pre-Order Traversal) |
 |
'Root → Left → Right' 순으로 방문 |
| 중위 순회 (In-Order Traversal) |
 |
'Left → Root → Right' 순으로 방문 |
| 후위 순회 (Post-Order Traversal) |
 |
'Left → Right→ Root' 순으로 방문 |
※ 수식 표현
수식을 표현할 때 Prefix, Infix, Postfix로 표현 할 수 있다.
▶ 3+2를 표현하는 방식
Prefix +32 Infix 3+2 Postfix 32+
▶ 트리 종류
㉮ 이진 탐색 트리 (Binary Search Tree)
- 이진 탐색 트리는 차수가 2 이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리이다.
- 이진 탐색 트리는 부모 노드보다 작은 값은 왼쪽으로 부모 노드보다 큰 값은 오른쪽 노드에 생성된다.
㉯ AVL 트리 (Adelson-Velsky and Landis Tree)
- AVL 트리는 두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형을 잡는 이진 탐색 트리이다.
㉰ 2-3 트리 (2-3 Tree)
- 2-3 트리는 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리이다.
- AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분을 줄인 트리이다.
㉱ 레드-블랙 트리 (Red-Black Tree)
- 레드-블랙 트리의 각 노드는 빨강 또는 검정의 색상을 가지고 있으며, 색깔에 따른 규칙을 통해 스스로 균형을 잡는 이진 탐색 트리이다.
② 그래프(Graph)
- 그래프는 노드와 노드를 연결하는 간선(Edge)을 하나로 모아 놓은 자료 구조이다.
- 트리는 사이클이 없는 그래프이다.
▶ 그래프의 유형
| 유형 | 그림 / 설명 |
| 방향 그래프 |  - 정점을 연결하는 선에 방향이 있는 그래프 - n개의 정점으로 구성된 방향 그래프의 최대 간선 수는 n(n-1) |
| 무방향 그래프 |  - 정점을 연결하는 선에 방향이 없는 그래프 - n개의 정점으로 구성된 무방향 그래프의 최대 간선 수는 n(n-1) / 2 |
▶ 그래프 용어정리
| 용어 | 설명 |
| 경로(Path) | 임의 정점에서 다른 정점으로 이르는 길 |
| 경로 길이(Path Length) | 경로상 있는 간선의 수 |
| 단순 경로(Simple Path) | 한 경로의 모든 간선이 다를 때의 경로 |
| 사이클(Cycle) | 동일 정점에서 시작과 끝이 이어지는 경로 |
▶ 그래프 탐색 방법
| 탐색 방법 | 설명 |
| 깊이 우선 탐색 (DFS: Depth-First Search) |
최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 |
| 너비 우선 탐색 (BFS: Breadth-Frist Search) |
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동 |
Reference
2022 수제비 정보처리기사 필기 1권+2권 합본세트 - 전2권
IT 비전공자를 위해 만들어진 수험서다. IT 분야의 최고 전문가 집단의 오랜 연구를 통한 정보처리기사 합격까지의 최단기 솔루션을 제안한다. 중요도에 따른 별점 체크, 두음쌤을 통한 암기비법
www.aladin.co.kr