[Python] 코딩테스트에서 요구하는 자료구조와 알고리즘

자료구조

array, linked list, stack, queue, deque, tree, graph, BST, heap, hash table (r-b tree, trie 몰라도 됨)

 

알고리즘

big-O, sorting, brute force, recursion, iteration, binary search, BFS/DFS, backtracking, divide and conquer, bit manipulation, two pointers, sliding window, dynamic programming (topological sort, union-find, KMP 몰라도 됨)

 

자료구조는 반드시 개념을 모두 익혀두어야 한다.

big-O 개념만 다 익히기

 

---

자료구조

1. array

 여러 개의 값을 순차적으로 저장

2. linked list

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장

 

배열 VS 연결리스트

배열은 물리적인 메모리 주소가 연속적이고, 연결리스트는 물리 메모리 주소가 연속적이지 않고 랜덤

배열은 삽입/삭제가 O(n)의 시간이 걸리지만, 동적으로 연결된 연결리스트는 삽입/삭제에 O(1)

3. stack

4. queue

5. deque

6. tree

7. graph

8. BST

9. heap

10. hash table