Уровень 3. Структуры данных и жадные алгоритмы

Стек, очередь, множества и словари, рекурсия, жадные алгоритмы и DSU — инструменты для задач среднего уровня.

Уровень инструментов: стек и очередь, set и map, рекурсивный перебор, жадные алгоритмы и DSU. После него вы сможете выбирать структуру данных под задачу, а не подгонять задачу под массив. Критерий готовности к уровню 4: вы пишете DSU и полный перебор с откатом по памяти, а для жадного решения можете объяснить, ПОЧЕМУ оно верно.

В этом разделе

  1. 1
    Стек и очередь

    Стек (LIFO) и очередь (FIFO): скобочные последовательности и порядок обработки.

  2. 2
    Множества и словари: set и map

    set и map: быстрые проверки принадлежности, подсчёт различных и частот за O(log n).

  3. 3
    Рекурсия и полный перебор

    Рекурсия и полный перебор: подмножества, перестановки и дерево вариантов.

  4. 4
    Жадные алгоритмы

    Жадные алгоритмы: локально лучший шаг, задача о непересекающихся интервалах, границы применимости.

  5. 5
    Система непересекающихся множеств (DSU)

    Система непересекающихся множеств: find и union со сжатием путей — почти O(1).

Доска