알고리즘을 읽기 쉬운 아이디어로, 코드와 함께 살펴봅니다.
trekhleb에서 영감을 받은 주제 카탈로그를 둘러보세요. 각 페이지는 간단한 설명, 실행 단계, 복잡도, 읽기 쉬운 JavaScript, 면접 노트, 흔한 실수, 추가 읽기를 포함한 완전한 이중 언어 학습 자료입니다.
Linked List
A linked list stores values in nodes. Each node keeps the value plus a reference to the next node, so the elements do not need to live next to each other in memory.
Doubly Linked List
Doubly Linked List is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Queue
A queue is FIFO: the first item that enters is the first item that leaves.
Stack
A stack is a LIFO structure: the last value pushed is the first value popped.
Deque
Deque is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Hash Table
A hash table maps keys to bucket locations using a hash function. It aims for very fast average lookup, insertion and deletion.
Heap
A heap is a complete tree, usually stored in an array, where every parent obeys a priority relation with its children. In a min-heap the smallest value stays at the root; in a max-heap the largest does.
Priority Queue
A priority queue removes the item with the highest (or lowest) priority first, not necessarily the item that arrived first.
Trie
Trie is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Tree
Tree is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Binary Search Tree
A binary search tree keeps smaller keys in the left subtree and larger keys in the right subtree, so search follows one branch at a time when the tree is balanced.
AVL Tree
An AVL tree is a self-balancing BST that keeps the height difference of each node's left and right subtrees within one, restoring balance with rotations.
Red-Black Tree
Red-Black Tree is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Segment Tree
Segment Tree is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Fenwick Tree
Fenwick Tree is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Graph
Graph is a data structure in the data structures family. This data structure organizes values and relationships so its most important operations have predictable costs.
Disjoint Set
Disjoint Set / Union-Find tracks a collection of non-overlapping groups and supports two key operations: find which group an item belongs to, and union two groups.
Bloom Filter
A Bloom filter is a space-efficient probabilistic set-membership structure. It can say 'definitely not present' or 'possibly present', so false positives are possible but false negatives are not in the standard design.
LRU Cache
An LRU cache evicts the least recently used item when capacity is full. The classic O(1) design combines a hash map with a doubly linked list.
Bit Manipulation
Bit Manipulation is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Binary Floating Point
Binary Floating Point is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Factorial
n! is the product 1 × 2 × … × n, with 0! defined as 1.
Fibonacci Number
The Fibonacci sequence starts from base values and each next number is the sum of the previous two.
Prime Factors
Prime Factors is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Primality Test
Primality Test is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Euclidean Algorithm
Euclid's algorithm finds gcd(a, b) by repeatedly replacing (a, b) with (b, a mod b) until the remainder becomes zero.
Least Common Multiple
Least Common Multiple is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Sieve of Eratosthenes
The Sieve of Eratosthenes finds all primes up to n by marking multiples of each discovered prime as composite.
Is Power of Two
Is Power of Two is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Pascal's Triangle
Pascal's Triangle is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Complex Number
Complex Number is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Radian & Degree
Radian & Degree is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Fast Powering
Fast Powering is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Horner's Method
Horner's Method is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Matrices
Matrices is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Euclidean Distance
Euclidean Distance is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Integer Partition
Integer Partition is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Square Root — Newton's Method
Square Root — Newton's Method is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Liu Hui π Algorithm
Liu Hui π Algorithm is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Discrete Fourier Transform
Discrete Fourier Transform is a algorithm in the math family. This mathematical algorithm turns a numeric identity or recurrence into a finite, computable procedure.
Cartesian Product
Cartesian Product is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Fisher–Yates Shuffle
Fisher–Yates Shuffle is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Power Set
Power Set is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Permutations
Permutations is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Combinations
Combinations is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Longest Common Subsequence
LCS finds the longest sequence of values that appears in both inputs in the same relative order, but not necessarily contiguously.
Longest Increasing Subsequence
Longest Increasing Subsequence is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Shortest Common Supersequence
Shortest Common Supersequence is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Knapsack Problem
In 0/1 knapsack, each item has a weight and value and may be chosen at most once. The goal is maximum total value without exceeding capacity.
Maximum Subarray
The maximum subarray problem asks for the contiguous segment with the largest sum. Kadane's algorithm solves it in O(n).
Combination Sum
Combination Sum is a algorithm in the sets & dynamic programming family. This problem is naturally expressed as smaller overlapping states/subproblems or as controlled generation of combinations.
Hamming Distance
Hamming Distance is a algorithm in the strings family. This string algorithm reasons about characters, prefixes, suffixes or edit/match state while avoiding unnecessary repeated comparisons.
Palindrome
A palindrome reads the same forward and backward after applying the problem's normalization rules.
Levenshtein Distance
Levenshtein distance is the minimum number of single-character insertions, deletions and substitutions needed to transform one string into another.
Knuth–Morris–Pratt
Knuth–Morris–Pratt is a algorithm in the strings family. This string algorithm reasons about characters, prefixes, suffixes or edit/match state while avoiding unnecessary repeated comparisons.
Z Algorithm
Z Algorithm is a algorithm in the strings family. This string algorithm reasons about characters, prefixes, suffixes or edit/match state while avoiding unnecessary repeated comparisons.
Rabin–Karp
Rabin–Karp is a algorithm in the strings family. This string algorithm reasons about characters, prefixes, suffixes or edit/match state while avoiding unnecessary repeated comparisons.
Longest Common Substring
Longest Common Substring is a algorithm in the strings family. This string algorithm reasons about characters, prefixes, suffixes or edit/match state while avoiding unnecessary repeated comparisons.
Regular Expression Matching
Regular Expression Matching is a algorithm in the strings family. This string algorithm reasons about characters, prefixes, suffixes or edit/match state while avoiding unnecessary repeated comparisons.
Linear Search
Linear search checks elements one by one until it finds the target or reaches the end.
Jump Search
Jump Search is a algorithm in the search family. This search algorithm narrows or scans a search space until the target is found or proven absent.
Binary Search
Binary search finds a target in a sorted search space by repeatedly discarding half of the remaining range.
Interpolation Search
Interpolation Search is a algorithm in the search family. This search algorithm narrows or scans a search space until the target is found or proven absent.
Bubble Sort
Bubble sort repeatedly compares adjacent values and swaps out-of-order pairs, causing large values to 'bubble' toward the end.
Selection Sort
Selection Sort is a algorithm in the sorting family. This sorting algorithm rearranges values into an ordered sequence using a specific comparison/distribution strategy.
Insertion Sort
Insertion sort grows a sorted prefix. It takes the next value and shifts larger values right until the new value can be inserted in the correct place.
Heap Sort
Heap Sort is a algorithm in the sorting family. This sorting algorithm rearranges values into an ordered sequence using a specific comparison/distribution strategy.
Merge Sort
Merge sort uses divide and conquer: split the array until pieces are trivial, then merge sorted pieces back together.
Quicksort
Quicksort picks a pivot, partitions values around it, then recursively sorts the partitions.
Shellsort
Shellsort is a algorithm in the sorting family. This sorting algorithm rearranges values into an ordered sequence using a specific comparison/distribution strategy.
Counting Sort
Counting sort avoids comparisons. It counts how many times each key appears, then reconstructs the output in key order.
Radix Sort
Radix Sort is a algorithm in the sorting family. This sorting algorithm rearranges values into an ordered sequence using a specific comparison/distribution strategy.
Bucket Sort
Bucket Sort is a algorithm in the sorting family. This sorting algorithm rearranges values into an ordered sequence using a specific comparison/distribution strategy.
Straight Traversal
Straight Traversal is a algorithm in the linked lists family. This linked-list algorithm walks references rather than indexed positions, so pointer/reference order is the main source of correctness.
Reverse Traversal
Reverse Traversal is a algorithm in the linked lists family. This linked-list algorithm walks references rather than indexed positions, so pointer/reference order is the main source of correctness.
Tree Depth-First Search
Tree Depth-First Search is a algorithm in the trees family. This tree traversal visits nodes in a deliberate order while exploiting the tree's parent/child hierarchy.
Tree Breadth-First Search
Tree Breadth-First Search is a algorithm in the trees family. This tree traversal visits nodes in a deliberate order while exploiting the tree's parent/child hierarchy.
Graph Depth-First Search
DFS explores one path as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack.
Graph Breadth-First Search
BFS explores a graph level by level using a queue. In an unweighted graph it finds shortest paths by number of edges.
Kruskal's Algorithm
Kruskal builds a minimum spanning tree by sorting edges by weight and taking the next cheapest edge that does not create a cycle.
Dijkstra's Algorithm
Dijkstra finds single-source shortest paths in a graph with non-negative edge weights by repeatedly finalizing the unsettled node with the smallest known distance.
Bellman–Ford Algorithm
Bellman–Ford computes single-source shortest paths even with negative edge weights, and can detect a reachable negative-weight cycle.
Floyd–Warshall Algorithm
Floyd–Warshall computes shortest paths between every pair of vertices with dynamic programming over allowed intermediate vertices.
Cycle Detection
Cycle Detection is a algorithm in the graphs family. This graph algorithm works over vertices and edges, usually using an adjacency list/matrix plus explicit state such as visited, distance, parent or indegree.
Prim's Algorithm
Prim grows one minimum spanning tree outward from a chosen start vertex, repeatedly adding the cheapest edge that connects the current tree to a new vertex.
Topological Sorting
Topological sorting produces a linear order of a directed acyclic graph (DAG) such that every directed edge u→v places u before v.
Articulation Points
Articulation Points is a algorithm in the graphs family. This graph algorithm works over vertices and edges, usually using an adjacency list/matrix plus explicit state such as visited, distance, parent or indegree.
Bridges
Bridges is a algorithm in the graphs family. This graph algorithm works over vertices and edges, usually using an adjacency list/matrix plus explicit state such as visited, distance, parent or indegree.
Eulerian Path & Circuit
Eulerian Path & Circuit is a algorithm in the graphs family. This graph algorithm works over vertices and edges, usually using an adjacency list/matrix plus explicit state such as visited, distance, parent or indegree.
Hamiltonian Cycle
Hamiltonian Cycle is a algorithm in the graphs family. This graph algorithm works over vertices and edges, usually using an adjacency list/matrix plus explicit state such as visited, distance, parent or indegree.
Strongly Connected Components — Kosaraju
Kosaraju finds strongly connected components in a directed graph using two DFS passes and the transposed graph.
Travelling Salesman Problem
Travelling Salesman Problem is a algorithm in the graphs family. This graph algorithm works over vertices and edges, usually using an adjacency list/matrix plus explicit state such as visited, distance, parent or indegree.
Polynomial Hash
Polynomial Hash is a algorithm in the cryptography family. This educational cipher/hash demonstrates a transformation over symbols or numeric state. It is useful for learning, but many classic ciphers are not secure for real systems.
Rail Fence Cipher
Rail Fence Cipher is a algorithm in the cryptography family. This educational cipher/hash demonstrates a transformation over symbols or numeric state. It is useful for learning, but many classic ciphers are not secure for real systems.
Caesar Cipher
Caesar Cipher is a algorithm in the cryptography family. This educational cipher/hash demonstrates a transformation over symbols or numeric state. It is useful for learning, but many classic ciphers are not secure for real systems.
Hill Cipher
Hill Cipher is a algorithm in the cryptography family. This educational cipher/hash demonstrates a transformation over symbols or numeric state. It is useful for learning, but many classic ciphers are not secure for real systems.
NanoNeuron
NanoNeuron is a algorithm in the machine learning family. This learning algorithm turns examples/data into a rule, grouping or prediction based on a distance, objective or simple model.
k-NN
k-NN is a algorithm in the machine learning family. This learning algorithm turns examples/data into a rule, grouping or prediction based on a distance, objective or simple model.
k-Means
k-Means is a algorithm in the machine learning family. This learning algorithm turns examples/data into a rule, grouping or prediction based on a distance, objective or simple model.
Seam Carving
Seam Carving is a algorithm in the image processing family. Seam carving resizes an image by removing or inserting low-energy paths rather than uniformly scaling every pixel.
Weighted Random
Weighted Random is a algorithm in the statistics family. This statistical sampling method converts weights into probabilities and samples accordingly.
Genetic Algorithm
Genetic Algorithm is a algorithm in the evolutionary algorithms family. A genetic algorithm searches a large solution space using populations, fitness, selection, crossover and mutation.
Tower of Hanoi
Tower of Hanoi is a algorithm in the classic problems family. This classic interview problem is mainly about recognizing the right pattern—two pointers, stack, greedy, DP or backtracking—rather than memorizing one code listing.
Square Matrix Rotation
Square Matrix Rotation is a algorithm in the classic problems family. This classic interview problem is mainly about recognizing the right pattern—two pointers, stack, greedy, DP or backtracking—rather than memorizing one code listing.
Jump Game
Jump Game is a algorithm in the classic problems family. This classic interview problem is mainly about recognizing the right pattern—two pointers, stack, greedy, DP or backtracking—rather than memorizing one code listing.
Unique Paths
Unique Paths is a algorithm in the classic problems family. This classic interview problem is mainly about recognizing the right pattern—two pointers, stack, greedy, DP or backtracking—rather than memorizing one code listing.
Rain Terraces / Trapping Rain Water
Trapping Rain Water asks how much water can sit above bars after rain. Water above index i is limited by the smaller of the tallest bar on its left and right.
Recursive Staircase
Recursive Staircase is a algorithm in the classic problems family. This classic interview problem is mainly about recognizing the right pattern—two pointers, stack, greedy, DP or backtracking—rather than memorizing one code listing.
Best Time to Buy/Sell Stocks
For the one-transaction stock problem, scan once while tracking the minimum price seen so far and the best profit achievable by selling today.
Valid Parentheses
Valid Parentheses checks whether every opening bracket is closed by the matching bracket in the correct nesting order. A stack models that nesting naturally.
N-Queens Problem
N-Queens places N queens on an N×N chessboard so that no two share a row, column or diagonal. Backtracking explores choices and abandons partial boards as soon as a conflict appears.
Knight's Tour
Knight's Tour is a algorithm in the classic problems family. This classic interview problem is mainly about recognizing the right pattern—two pointers, stack, greedy, DP or backtracking—rather than memorizing one code listing.