4단원 요약정리

1. 선형 자료구조

① 데이터가 연속적으로 나열되는 자료구조
② 종류

- 배열: 정해진 크기만큼의 데이터가 일렬로 저장되는 정적 자료구조

- 연결 리스트: 크기가 정해져 있지 않은 동적 자료구조, 노드로 구성됨

- 스택: 마지막에 들어온 데이터가 먼저 나가는 구조(LIFO)

- 큐: 먼저 들어온 데이터가 먼저 나가는 구조(FIFO)

- 덱: 자료구조의 양쪽 끝에서 데이터 추가와 삭제가 모두 가능한 구조

 

2. 비선형 자료구조

① 하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는 자료구조

② 그래프, 트리, 우선순위, 큐, 힙, 해시 테이블이 해당함

 

3. 그래프

① 데이터를 포함하는 정점과 정점을 잇는 간선으로 구성
② 사이클을 가질 수 있음
③ 탐색 방법: BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

 

4. 트리

① 그래프의 한 종류로, 사이클이 없어서 계층 관계를 표현할 수 있음
② 이진 트리: 자식 노드의 개수가 최대 2개인 트리

- 완전 이진 트리: 트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있는 이진 트리로, 마지막 레벨은 왼쪽에서 오른쪽으로 차례대로 노드가 채워짐

- 포화 이진 트리: 트리의 마지막 레벨까지 모든 레벨에 노드가 채워져 있는 이진 트리

- 이진 탐색 트리: 왼쪽 자식 노드는 부모 노드보다 작은 값을 가지고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 이진 트리

- 자가 균형 이진 탐색 트리: 삽입 연산과 삭제 연산을 수행해도 트리의 균형을 유지하는 트리(레드-블랙 트리, AVL 트리)

 

5. 힙

① 최댓값 또는 최솟값을 빠르게 찾을 수 있는 완전 이진 트리
② 최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리

③ 최소 힙: 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리

 

6. 해시 테이블

① 키에 대한 값을 저장하는 형태의 자료구조
② 키를 해시 함수에 넣어 얻은 해시를 통해 값에 접근
③ 해시 충돌: 서로 다른 키를 해시 함수에 넣었을 때 같은 해시가 나오는 현상
④ 해시 충돌 해결 방법

- 체이닝: 같은 해시가 나오는 값을 연결 리스트에 저장

- 개방 주소법: 비어 있는 공간에 데이터 저장(선형 조사법, 이차 조사법, 이중 해상)