Eche un vistazo a esta respuesta de Brian Bi a una pregunta muy similar [enlace directo al final del texto].
La programación dinámica (DP) parece dar cuenta de una pluralidad (algunos estiman hasta un tercio) de los problemas del concurso. Por supuesto, DP tampoco es un algoritmo único que solo puede aprender una vez y retener, por lo que tal vez esto no responda a su pregunta.
Supongo que también depende de si considera las estructuras de datos en la misma categoría que los algoritmos. Ciertamente, hay algunas estructuras de datos con las que debería estar familiarizado si desea tener éxito en la programación de competencias. Los más importantes son los árboles de rango (conocidos también como árboles de intervalo o árboles de segmento) y los árboles indexados binarios (BIT), también conocidos como árboles Fenwick. Además, muchos algoritmos DP hacen uso de una matriz de suma de prefijos.
- Si hipotéticamente encontré un algoritmo que genera rendimientos comerciales al 100% anualmente, ¿qué debo hacer con él?
- ¿Cuál es la forma más rápida y eficiente de hacer una sustitución / sustitución de cadenas dentro de una cadena grande con JavaScript?
- ¿Qué es un algoritmo en C?
- ¿Se podría explicar y crear inteligencia artificial utilizando algoritmos?
- ¿Cuáles son las aplicaciones prácticas / de la vida real / industriales de Dijkstra, Kruskal y Algortithm de Prim?
Los algoritmos más esenciales que se me ocurren son los siguientes, sin ningún orden en particular. Sin embargo, es posible que se sienta decepcionado por la poca frecuencia con que algunos de estos aparecen en los concursos. La mayoría de los problemas que no son DP parecen ser de la variedad ” ad hoc con estructuras de datos”, y simplemente tiene que practicar para ser bueno en ellos.
(Para ser claros, nuevamente, enumero a continuación solo los algoritmos que toman un solo conjunto de entrada, calculan alguna función del mismo y no llevan estado entre las entradas. Esto los distingue de las estructuras de datos, que por definición mantienen el estado, y las categorías de algoritmos y técnicas algorítmicas como DP, que no tienen alguna función específica que calculan).
- Tamiz de Eratóstenes, u otro tamiz de números primos
- Búsqueda de profundidad primero
- Búsqueda de amplitud
- Algoritmo de Dijkstra
- Algoritmo de Floyd-Warshall
- Ya sea el algoritmo de Kruskal o Prim
- Alguna implementación de la clasificación topológica, como mediante el uso de DFS
- Casco convexo (recomiendo el algoritmo de cadenas monótonas)
- Compresión coordinada
- Edmonds – Karp, u otra implementación del método Ford – Fulkerson; o un algoritmo de flujo previo; o, si está preparando un libro de códigos ACM, el algoritmo de Dinic. (Nota: no se permite que el flujo máximo aparezca en el IOI, pero puede aparecer en los concursos de selección de equipos nacionales)
La respuesta de Brian Bi a ¿Cuáles son los 10 algoritmos que uno debe conocer para resolver la mayoría de los problemas de algoritmos?
