1.정렬 알고리즘
- O(N^2)
Insertion (대부분이 정렬되어 있을 시 가장 빠름.. O(N) )
Selection
Bubble(제일 느림)
- O(NlogN)
Merge (Divide and Conquer)
Heap ( BuildHeap시 O(nlogn)이 아닌 O(N) )
Quicksort (최악의 경우 이론 상 O(N^2). 하지만 이중에서 제일 빠르다. pivot(고르는 기준 다양)을 기준으로 작은거 큰거 나누고 다시 잭귀적으로..)
2. 탐색 알고리즘
BFS / DFS
Dijkstra / A*(BestFS)
3. Minimum Spanning Tree(MST, 최소신장트리)
Kruskal, Prim 방법.. (크루스컬은 쉬움. 프림은 프론티어 중에서 고름. 사이클 생기지 않게 매 순간순간 그리디하게 결정)
4. 스택 : LIFO. 큐 두 개로 구현 가능?
5. 큐 : FIFO. 스택 두 개로 구현 가능?
6. Cycle Detection : visit 배열로 검사 or slow, fast 두개의 포인터가 겹치는지 여부 검사
7. 링크드 리스트 (singly(Head), doubly(Head, Tail) 두 개다 시간복잡도 같음.
search ... O(n) / insert ... O(1) / delete ... O(1)
8. 배열. 인덱스로 접근
search ... O(1) / insert ... O(n) / delete ... O(n)
크게 만들어놓고 꽉 찰 때에만 행렬의 크기를 늘려준다면 ?? --> Amortized(분할상환). insert, delete가 O(n)이 아니게 된다.
9. Hash
Hash function : 임의의 길이의 데이터를 고정된 크기의 데이터로 매핑.. (MD5(128), SHA-1(160), SHA-2(256,512))
Hash Table : H(x)값을 인덱스로 하고 이에 매칭되는 값을 가지는 key-value 형식의 자료구조
해쉬함수의 결과가 충돌하게 된다면?
->개방 주소법(Open Addressing) : Linearr Probing, Quadratic Probing
->Seperate Chaining : 링크드리스트처럼 주렁주렁 달아놓음
해쉬테이블이 가득차가면 resize를 통해 크기 변경.
resizing하면 다시 재배열 해줘야함... 현업에서 매우 민감한 문제. cpu이용률 낮을때, 밤에 진행.
resizing 오버헤드를 최소화하는 법 -> Consistent Hashing(일관된 해싱)
