[Data Structure] 꼭 알아야 할 자료구조와 알고리즘 테이블

어제자로 학기로부터 해방되어,

평소 꼭 정복해보고 싶었던 자료구조, 

그리고 알고리즘에 대해 약간의 정리를 해볼까 합니다.

일종의 Cheatsheet인데요, 나중엔 머릿속에 다 들어와 있겠죠?

 

코딩테스트 풀이 때, 시간 초과와 메모리 초과로부터 좀 해방될 수 있었으면 좋겠네요.

Data Structures

 

Data Structure	Purpose	Time Complexity	(Avg)Space Complexity	Additional Notes
Array	Stores elements of the same type in contiguous memory locations.	Access: O(1), Search: O(n), Insertion: O(n), Deletion: O(n)	O(n)	Fixed size, efficient for indexing.
Linked List	Stores elements in nodes, each node links to the next node.	Access: O(n), Search: O(n), Insertion: O(1), Deletion: O(1)	O(n)	Dynamic size, efficient for insertions and deletions.
Stack	LIFO (Last In, First Out) data structure.	Access: O(n), Search: O(n), Insertion: O(1), Deletion: O(1)	O(n)	Used in function calls, undo mechanisms.
Queue	FIFO (First In, First Out) data structure.	Access: O(n), Search: O(n), Insertion: O(1), Deletion: O(1)	O(n)	Used in BFS, scheduling algorithms.
Deque	Double-ended queue supporting insertion and deletion from both ends.	Access: O(n), Search: O(n), Insertion: O(1), Deletion: O(1)	O(n)	Generalization of stack and queue.
Tree	Hierarchical structure for storing data.	Varies based on type of tree.	O(n)	Used in databases, file systems.
Graph	Represents relationships between nodes.	Varies based on type of graph and its representation.	O(V + E)	Used in social networks, routing algorithms.
Binary Search Tree (BST)	A tree in which each parent node has at most two children, with the left child less than the parent and the right child greater.	Access: O(log n), Search: O(log n), Insertion: O(log n), Deletion: O(log n)	O(n)	Maintains sorted data, faster operations than a regular tree.
Heap	A specialized tree-based structure that satisfies the heap property.	Access: O(1), Search: O(n), Insertion: O(log n), Deletion: O(log n)	O(n)	Used in priority queues, sorting algorithms.
Hash Table	Stores key-value pairs for efficient data retrieval.	Access: O(1), Search: O(1), Insertion: O(1), Deletion: O(1)	O(n)	Collision handling is crucial, resizing can be costly.

Algorithms

 

Algorithm	PurposeTime	Complexity	(Avg)Space Complexity	Additional Notes
Big-O Notation	Describes the upper bound of time or space complexity.	Varies based on context.	Varies based on context.	Used to estimate the worst-case scenario of an algorithm.
Sorting	Arranges data in a specified order.	Varies: O(n^2) for simple sorts, O(n log n) for efficient sorts.	Varies: O(1) for in-place sorts, O(n) for others.	Includes bubble, merge, quick, heap sort, etc.
Brute Force	Tries all possible solutions.	O(n^n) or worse, depending on the problem.	O(1)	Not efficient for large datasets.
Recursion	Function calls itself with a subset of the original problem.	Varies, often O(2^n) or O(n!).	O(n) due to call stack.	Can lead to stack overflow if not designed properly.
Iteration	Repeats a block of code until a condition is met.	O(n) in many cases.	O(1)	Often more efficient than recursion.
Binary Search	Finds an element in a sorted array.	O(log n)	O(1)	Requires sorted input.
Breadth-First Search (BFS)	Explores all nodes at the present depth prior to moving on to the nodes at the next depth level.	O(V + E)	O(V)	Useful in shortest path problems.
Depth-First Search (DFS)	Explores as far as possible along each branch before backtracking.	O(V + E)	O(V)	Useful in pathfinding, puzzle solving.
Backtracking	Solves problems by trying to build a solution incrementally.	Varies, often exponential.	O(n) for the recursion stack.	Involves decision making and pruning.
Divide and Conquer	Breaks a problem into subproblems of the same type.	Varies, often O(n log n).	O(n) for the stack space in recursive calls.	Used in quicksort, mergesort.
Bit Manipulation	Performs operations directly on binary digits.	O(1) for basic operations.	O(1)	Includes AND, OR, XOR, bit shifting.
Two Pointers	Uses two pointers to traverse data structures in one pass.	O(n)	O(1)	Effective in sorted arrays or linked lists. ​​
Sliding Window	Moves a window to capture a subset of data.	O(n)	O(k), where k is the size of the window.	Useful in problems like maximum sum of subarray.
Dynamic Programming	Solves complex problems by breaking them into simpler subproblems.	O(n^2) or better, varies with problem.	O(n) or more, depending on storage of subproblem results.	Used in problems like Fibonacci, shortest paths.