-
[정보처리기사 필기] 자료 구조 (Data Structure)CS/정보처리기사 2023. 6. 29. 20:44반응형
¶ 자료 구조의 개념
- 자료 구조는 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조이다.
- 자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킨다.
¶ 자료 구조의 분류
구조 설명 종류 선형 구조 데이터를 연속적으로 연결한 자료 구조 리스트, 스택, 큐, 데크 비선형 구조 데이터를 비연속적으로 연결한 자료 구조 트리, 그래프 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
2022 수제비 정보처리기사 필기 1권+2권 합본세트 - 전2권
IT 비전공자를 위해 만들어진 수험서다. IT 분야의 최고 전문가 집단의 오랜 연구를 통한 정보처리기사 합격까지의 최단기 솔루션을 제안한다. 중요도에 따른 별점 체크, 두음쌤을 통한 암기비법
www.aladin.co.kr
반응형'CS > 정보처리기사' 카테고리의 다른 글
[정보처리기사 실기] 과목4 - 통합 구현, 오답노트 (0) 2023.07.09 [정보처리기사 실기] 과목3 - 데이터 입출력 구현, 오답노트 (0) 2023.07.06 [정보처리기사 실기] 과목2 - 화면 설계, 오답노트 (0) 2023.07.04 [정보처리기사 실기] 과목1 - 요구사항 확인, 오답노트 (0) 2023.07.03 [정보처리기사 필기] 알고리즘 (Algorithm) (0) 2023.06.29