[정보처리기사 필기] 자료 구조 (Data Structure)

 

¶ 자료 구조의 개념

• 자료 구조는 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조이다.
• 자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킨다.

 

¶ 자료 구조의 분류

구조	설명	종류
선형 구조	데이터를 연속적으로 연결한 자료 구조	리스트, 스택, 큐, 데크
비선형 구조	데이터를 비연속적으로 연결한 자료 구조	트리, 그래프

 

https://hyeonukdev.github.io/2020/05/26/Engineer_Information_Processing/ch05_%EB%8D%B0%EC%9D%B4%ED%84%B0%EC%9E%85%EC%B6%9C%EB%A0%A5%EA%B5%AC%ED%98%84/%EB%85%BC%EB%A6%AC%EB%8D%B0%EC%9D%B4%ED%84%B0%EC%A0%80%EC%9E%A5%EC%86%8C%ED%99%95%EC%9D%B8/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/

 

---

 

선형 구조

 

① 리스트(List)

    ▶ 리스트의 종류

종류	설명
선형 리스트 (Linear List)	- 배열과 같이 연속되는 기억 장소에 저장되는 리스트 - 선형 리스트의 대표적인 구조로는 배열(Array) 등이 있음 - 가장 간편한 자료 구조이며, 접근 구조가 빠름 - 자료의 삽입, 삭제 시 기존 자료의 이동이 필요
연결 리스트 (Linked List)	- 노드의 포인터 부분으로 서로 연결시킨 리스트 - 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분 - 노드의 삽입, 삭제가 선형 리스트와 달리 편리 - 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요 - 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림

 

선형 리스트는 연속되는 기억 장소, 연결 리스트는 포인터 연결

 

https://infinitt.tistory.com/279

 

https://infinitt.tistory.com/279

 

② 스택(Stack)

    스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO(Last-In First-Out) 형식의 자료 구조이다.

 

https://www.stechstar.com/user/zbxe/AlgorithmPython/51863

 

• 한 방향으로만 PUSH와 POP을 이용하여 자료를 넣고 꺼낸다.
• TOP은 스택에서 가장 위에 있는 데이터로, 스택 포인터(Stack Pointer) 라고도 불린다.

 

    ▶ 스택 연산

연산	설명
PUSH	데이터를 차례대로 스택에 넣는 연산
POP	스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산

 

    ▶ 스택 응용 분야

분야	설명
인터럽트의 처리	현재 진행 중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행 중이던 명령어 위치를 스택에서 POP을 통해 받아옴
함수 호출 (재귀 호출 포함)	함수를 호출 시 현재 진행 중인 명령어 주소를 스택에 저장
후위표현 연산	Postfix 를 계산할 때 사용
깊이 우선 탐색 (DFS: Depth-Frist Search)	깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾음

 

③ 큐(Queue)

    큐는 한쪽 끝에서는 삽입 작업이 이뤄지고, 반대쪽 끝에서는 삭제 작업이 이루어지는 FIFO(First-In First-Out) 형식의 자료 구조이다.

 

https://code-lab1.tistory.com/6

 

• 한쪽에서는 ENGUEUE 연산을 이용하여 데이터를 넣고, 한쪽에서는 DEQUEUE 연산을 이용하여 데이터를 꺼낸다.
• 데이터가 꺼내는 쪽에서 가장 가까운 데이터를 Front라고 하고, 데이터를 넣는 쪽에서 가장 가까운 데이터를 Rear라고 한다.

 

    ▶ 큐 연산

연산	설명
ENQUEUE	데이터를 차례대로 넣는 연산
DEQUEUE	처음 저장된 데이터부터 하나씩 꺼내는 연산

 

④ 데크 (Deque: Double Ended Queue)

    데크는 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조이다.

 

https://iq.opengenus.org/double-ended-queue-deque/

 

• 두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다.
• 데크를 이용한 스택과 큐의 구현이 가능하다.

 

    ▶ 데크 연산

연산	설명
PUSH	데이터를 차례대로 데크에 넣는 연산
POP	데크에서 Front와 Rear에 있는 데이터를 하나씩 꺼내는 연산

 

---

 

비선형 구조

 

① 트리

• 트리는 데이터들을 계층화시킨 자료 구조이다.
• 그래프의 특수한 형태로 노드와 선분(Branch)으로 되어 있고, 정점 사이에 사이클이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조이다.
• 인덱스를 조작하는 방법으로 가장 많이 사용하는 구조이다.
• 트리는 노드와 노드를 연결하는 링크로 구성된다.
• 배열과 달리 노드들이 포인터로 연결되어 노드의 상한선이 없다.

 

https://heung-bae-lee.github.io/2020/05/02/data_structure_06/#lg=1&slide=0

 

    ▶ 트리 용어

용어	설명
루트 노드 (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 이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리이다.
• 이진 탐색 트리는 부모 노드보다 작은 값은 왼쪽으로 부모 노드보다 큰 값은 오른쪽 노드에 생성된다.

 

https://velog.io/@changhee09/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC

 

㉯ 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

• https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=284071828

2022 수제비 정보처리기사 필기 1권+2권 합본세트 - 전2권