유명한 문제는 75개입니다 에서 본 목록입니다.
문제마다 Input, Output 을 한 줄씩 적었습니다. 이름만으로는
뭘 하는 문제인지 알 수 없는 것들이 많아서요.
원문이 아니라 제가 줄여 쓴 것입니다. 정확한 정의는 Stony Brook Algorithm
Repository(algorist.com)의 각 항목에 있습니다.
| 문제 | In | Out |
|---|
| Dictionaries | n records, each with a key | a structure that finds, inserts and deletes a record by its key |
| Priority Queues | records with ordered keys | a structure that always hands back the smallest, and stays fast as records come and go |
| Suffix Trees and Arrays | a reference string | a structure that finds every place a query string sits inside it |
| Graph Data Structures | a graph | a representation that is small to store and quick to walk |
| Set Data Structures | a universe of objects and a family of subsets | a representation that tests membership and takes unions and intersections quickly |
| Kd-Trees | n points in k dimensions | a tree splitting the space so each point sits in its own region |
| 문제 | In | Out |
|---|
| Sorting | n items | the same items in increasing order |
| Searching | n keys and a query key | where the query sits among them |
| Median and Selection | n numbers | the one with half below it and half above |
| Generating Permutations | an integer n | every ordering of n things, or a random one, or the next one |
| Generating Subsets | an integer n | every subset of 1..n, or a random one, or the next one |
| Generating Partitions | an integer n | every way to split n, or a random one, or the next one |
| Generating Graphs | a vertex count, an edge count, or an edge probability | a graph that meets them — every such graph, a random one, or the next |
| Calendrical Calculations | a month, a day and a year | the weekday it fell on |
| Job Scheduling | jobs with "this one before that one" constraints | a schedule finishing in the least time, or on the fewest machines |
| Satisfiability | clauses built from ands, ors and nots on boolean variables | whether some assignment makes every clause true |
| 문제 | In | Out |
|---|
| Clique | a graph | the largest set of vertices all joined to each other |
| Independent Set | a graph | the largest set of vertices with no edge between any two |
| Vertex Cover | a graph | the smallest set of vertices touching every edge |
| Traveling Salesman Problem | a weighted graph | the cheapest cycle through every vertex exactly once |
| Hamiltonian Cycle | a graph | an order visiting every vertex exactly once |
| Graph Partition | a weighted graph, a size bound and a cost bound | a split into parts no bigger than the size bound, cutting no more than the cost bound |
| Vertex Coloring | a graph | a coloring of the vertices using the fewest colors, so that no two neighbors match |
| Edge Coloring | a graph | the fewest colors for the edges so that edges meeting at a vertex differ |
| Graph Isomorphism | two graphs | a relabeling that turns one graph into the other, if such a relabeling exists |
| Steiner Tree | a graph and a subset of its vertices | the smallest tree connecting that subset |
| Feedback Edge/Vertex Set | a directed graph | the fewest edges or vertices to remove so that no cycle is left |
| 문제 | In | Out |
|---|
| Robust Geometric Primitives | a point and a segment, or two segments | which side the point is on, or whether the segments cross — without rounding errors giving a wrong answer |
| Convex Hull | n points | the smallest convex polygon holding them all |
| Triangulation | a point set or a polyhedron | its interior cut into triangles |
| Voronoi Diagrams | n points | the region around each point closer to it than to any other |
| Nearest Neighbor Search | n points and a query point | the closest one |
| Range Search | n points and a query polygon | the points falling inside it |
| Point Location | a plane cut into regions, and a query point | the region it falls in |
| Intersection Detection | segments, or two polygons | which pairs cross, or the shape they share |
| Bin Packing | items with sizes, bins with capacities | a packing using as few bins as possible |
| Medial-Axis Transform | a polygon | the points inside that have more than one nearest point on the boundary — its skeleton |
| Polygon Partitioning | a polygon | a cut into as few simple pieces as possible, usually convex ones |
| Simplifying Polygons | a polygon with n vertices | one with fewer vertices that still looks like it |
| Shape Similarity | two shapes | how alike they are |
| Motion Planning | a robot, a room with obstacles, a start and an end | the shortest path that gets the robot across without hitting anything |
| Maintaining Line Arrangements | n lines and segments | the cells, edges and vertices they cut the plane into |
| Minkowski Sum | two point sets or polygons | every sum of a point from one and a point from the other |