😄 제가 대학원 준비과정에서 정리했던 컴퓨터공학과 기본 과목을 공유합니다!
📬 댓글로 이메일 남겨주시면 한글 파일 보내드리겠습니다!
PS: 이현경 취업 성공 기원
📚 Data Structure
1. Array
논리적 저장순서와 물리적 저장순서가 일치하는 자료구조
Index를 이용해 element에 접근
정렬을 위해 삽입/삭제에서 O(n)의 추가적인 cost 발생
2. Linked List
각 node에 element와 다음 노드의 정보를 저장하는 자료구조
Array의 time complexity 문제를 O(1)로 해결 가능
Search 하는 과정에서 O(n)의 time complexity를 가져
결과적으로 삽입/삭제에서 O(n)의 추가적인 cost 발생
3. Stack
선형 자료구조의 일종으로 LIFO
4. Queue
선형 자료구조의 일종으로 FIFO
5. Graph
vertex와 edge로 이루어진 비선형 자료구조
1) 표현법
: adjacent matrix, adjacent list
2) Search
- DFS (Depth First Search)
한 vertex와 연결된 하나의 vertex를 우선적으로 탐색
(Stack 활용)
- BFS (Breath First Search)
한 vertex와 연결된 모든 vertex로 나아가는 탐색
(Queue 활용)
6. Tree
계층적 관계를 표현하기 위해 만들어진 비선형 자료구조
Cycle을 가지지 않는 연결 그래프
1) Binary Tree
각각의 노드가 최대 2개의 서브트리로 나누어지는 트리
서브트리는 Binary Tree의 조건을 따름
재귀적으로 조건을 확인하기 때문에 공집합도 포함
2) BST (Binary Search Tree)
R child node > Parent node > L child node라면 O(log n)의 time complexity를 가진다.
3) Binary Heap
Complete binary tree를 보통 배열로 표현한 자료구조
parent node와 child 노드가 규칙을 가지며, P > C 인 경우 Max heap, P < C인 경우 Min heap
4) Red Black Tree (RBT)
node에 black/red의 색이라는 속성을 부여해
삽입/삭제/검색을 효율적으로 수행하도록 구현된 Tree
5) Spanning Tree
그래프 내의 모든 vertex를 포함하는 Tree
- MST (Minimum Spanning Tree)
가중치 그래프에서 비용을 최소로 하는 ST
Kruskal || Prim 알고리즘으로 생성 가능
7. Hash Table
(key, value) 형태로 데이터를 저장하는 자료구조
1) Hash Function
고유한 Index값을 설정하기 위해 Hash 함수 사용
- Division Method : 테이블 크기로 나누어 계산
- Digit Folding : Key의 문자열 -> ASCII 코드 합해 계산
- Multiplication Method : (kAmod1) × m
- Universal Hashing : 다수의 해시함수 집합 H에서
- 무작위로 해시함수를 선택해 해시값을 만드는 기법
2) Hash 충돌
두 키에 대해 해시함수를 돌렸을 때 나온 값이 동일
- 분리 연결법 (Separate Chaining)
동일 index로 인해서 충돌이 발생하면
그 index가 가리키는 Linked list에 노드를 추가해 값을 추가
- 개방 주소법 (Open Addressing)
비어있는 해시 테이블의 공간을 활용하는 방법
- Linear Probing
현재의 버킷 index로부터 고정폭 만큼씩 이동하여
차례대로 검색해 비어있는 버킷에 데이터를 저장한다.
- Quadratic Probing
해시의 저장순서 폭을 제곱으로 저장하는 방식이다.
예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고
다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식
- Double Hashing Probing
해싱된 값을 한 번 더 해싱해 해시의 규칙성을 없애는 방식
다른 방법들보다 많은 연산을 하게 된다.
