비선형 자료구조?
하나의 데이터에 N개이 데이터가 이어지는 구조. 1:N, N:N 구조로 되어있다.
계층적 구조를 나태내기에 편리.
그래프?
데이터를 포함하는 정점vertex(노드node)과 정점edge을 잇는 간선으로 구성되어 있다.
G = (V,E)
1. 무방향 그래프
간선에 방향성이 없는 그래프.
정점 개수가 n일때 최대 간선의 개수는 n x (n-1) / 2이다.
2. 방향 그래프
간선에 방향성이 있는 그래프.
정점 개수가 n일때 최대 간선의 개수는 n x (n-1) 이다.
경로 탐색
1. 너비 우선 탐색(BFS)
탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식.
먼저 탐색하는 정점과 인접한 정점을 탐색하면서 큐에 삽입한다.
큐에 넣기 전에 이전에 방문했는지 확인 필요.
2. 깊이 우선 탐색(DFS)
시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색.
재귀 호출 or 스택으로 구현.
※알고리즘, 코테 정리하면서 더 깊게 작성할 예정.
트리?
그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현할 수 있다.
이진트리?
자식 노드가 최대 2개인 트리.
- 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며 마지막 오른쪽 노드 한개가 비어 있으면 완전 이진트리. 오른쪽 노드 한개만 채워져 있으면 불완전 이진 트리다.
- 포화 이진 트리 : 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리. 포화 이진 트리는 완전 이진 트리로 볼 수 있다.
- 이진 탐색 트리(BST) : 왼쪽 서브 트리는 해당 노드의 값 보다 작은 값을 가진 노드로 구성되고, 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리다.
균형 잡힌 이진 탐색 트리는 루트 노드와 가까운 노드 일수록 검색해야 하는 노드 개수가 절반으로 줄어듬.
검색시 복잡도 : O(logn)
불균형 일시 : O(n) 이므로 이진 탐색 트리를 이용하는 장점이 사라진다.
우선순위 큐?
우선순위가 높은 데이터가 먼저 나오는 자료구조.
데이터 삭제 연산 수행시 우선순위가 가장 높은 데이터를 얻을 수 있다.
구현 방식은 배열, 연결 리스트, 완전 이진트리(힙) 이있다. 일반적으로는 힙으로 구현.
| 구현 방법 | 삽입 복잡도 | 삭제 복잡도 |
| 배열 | O(1) | O(n) |
| 연결 리스트 | O(1) | O(n) |
| 배열(정렬o) | O(n) | O(1) |
| 연결 리스트(정렬o) | O(n) | O(1) |
| 힙 | O(logn) | O(logn) |
힙?
완전 이진 트리로, 최대값 또는 최솟값을 빠르게 찾을 수 있는 자료구조.
- 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
- 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
해시 테이블
키-값 으로 저장하는 자료구조.
해시 함수를 사용해 해시를 얻을 수 있다.
해시란 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값이다.
해시 충돌?
서로 다른 키에 대해 같은 해시가 도출되는 것.
해시 충돌 문제 해결?
- 체이닝 : 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식. 연결 리스트에 노드를 저장하므로 저장 공간에 대한 제약이 적다는 장점이 있지만 하나의 해시에 노드가 몰릴 수도 있다.
- 개방 주소법 : 해시 충돌 시 해시가 아닌 비어 있는 공간에 값을 저장하는 방식. ex) 선형 조사법, 이차 조사법, 이중 해싱
'CS > 자료구조' 카테고리의 다른 글
| 자료구조 - 빅오표기법, 선형 자료구조 (0) | 2024.06.21 |
|---|