내장 라이브러리가 있는 선형 자료구조
- 정적 배열
- 동적으로 크기가 변하는 배열
https://www.slideshare.net/SOPT/sopt-01
정렬
- O(n^2) : 버블, 선택, 삽입
- O(nlogn) : 병합, 힙, 퀵
- O(n) : 계수, 기수, 버킷
https://www.slideshare.net/SOPT/sopt-03
탐색
- O(n) : 선형
- O(nlogn) : 이진
- O(1) : 해싱
linked list
- 검색에 비효율적
- 삽입, 삭제에 용이
stack
- LIFO 구조
queue
- FIFO 구조
https://www.slideshare.net/SOPT/sopt-02
내장 라이브러리가 있는 비선형 자료구조
https://www.slideshare.net/SOPT/sopt-04-53869519
binary search tree
- 검색, 삽입, 삭제가 O(logn)
AVL tree
http://devidea.tistory.com/entry/AVL-Tree?category=540720
http://devidea.tistory.com/entry/AVL-Tree-2-%EC%82%AD%EC%A0%9C?category=540720
https://www.slideshare.net/SOPT/sopt-05-avl
Red-Black 트리
http://ddmix.blogspot.kr/2015/02/cppalgo-19-red-black-tree.html
heap
- 완전 이진 트리
- 부모노드의 키 값이 자식노드의 키값보다 항상 큰 heap이 최대 heap, 반대이면 최소 heap
- 우선순위 큐를 모델링 할 때 유용(검색, 삽입 O(logn))
http://coderkoo.tistory.com/10
자체적인 라이브러리가 필요한 자료구조
그래프
- 표현 : 인접 행렬 그래프, 인접 리스트 그래프
- 탐색 : BFS, DFS, Dijkstra, Floyd Washall
union find (상호 배타적 집합)
https://sungjk.github.io/2016/06/02/DisjointSet.html
segment tree (구간 트리)
https://www.acmicpc.net/blog/view/9
이진 인덱스 트리
http://www.crocus.co.kr/666