Как научиться решать алгоритмические задачи

Короткий ответ. Знать язык и решать алгоритмические задачи это два разных навыка. Второй стоит на пяти идеях, которые никто не перечисляет. Сколько стоит операция. Какая структура подходит под вопрос. Какой инвариант держит цикл. Как прогнать пример руками. Как читать ограничения. Каждая идея умещается в абзац, все пять в неделю.

1. Сколько стоит операция

Ты умеешь взять элемент массива. Вопрос в том, сколько это стоит.

Обращение по индексу это один шаг при любом размере. Поиск в неотсортированном массиве это шаг на каждый элемент.

Взять значение по ключу в ассоциативном массиве это один шаг. Сортировка это n log n.

Пять фактов. Без них выбор алгоритма это подбрасывание монеты.

Нельзя сравнить два плана, у которых нет цены. Как их оценивать, разобрано в статье Big O простыми словами.

2. Выбор структуры

Новички держат всё в массивах, потому что массивам их и учили.

Спрашивать надо другое: что ты будешь делать чаще всего.

«Видел ли я это раньше» указывает на множество. «Какое значение у этого ключа» на словарь.

«Дай самое маленькое из виденных» на кучу. Важен порядок, оставляй массив.

Половина задач решается правильным выбором здесь. Остальной код дописывается сам.

3. Инвариант

Инвариант это одно предложение, которое верно на каждом проходе цикла.

«Всё слева от i уже отсортировано». «Сумма окна всегда не больше k».

Цикл без такого предложения пишут перебором.

Добавил единицу, тест прошёл. Почему, ты так и не узнал.

Пиши предложение до цикла.

Большинство ошибок на единицу исчезает. Плюс один либо сохраняет предложение верным, либо нет.

4. Прогнать пример руками

Возьми четыре элемента и реши на бумаге. Медленно.

Потом посмотри, что делала рука. Сравнила две вещи, запомнила лучшее, пошла дальше.

Эти три шага и есть алгоритм.

Почти любая техника из первой половины программы формализует то, что люди делают руками.

Пропустил шаг, и код выглядит взявшимся из ниоткуда.

5. Читать ограничения как инструкцию

«n до 1000» разрешает квадрат. «n до 200000» его запрещает.

Одна строка часто определяет весь подход. Новички читают её как мелочь. Полная таблица границ собрана в статье таблица сложности алгоритмов.

Чего здесь нет

Ни одна из пяти вещей не про интеллект и не про математику.

Пять вещей умещаются в пять маленьких кусков знания, каждый на абзац. Туториалы считают, что они у тебя есть.

Любой, кто полгода писал рабочий код, укладывает все пять в неделю.

Невозможным это кажется из-за порядка подачи. Тебе дали сороковой шаг под видом пятого.

Где начинается лестница

AlgoPath начинается до первого алгоритма, с бесплатного урока что такое алгоритм.

Цена операций, структуры, инварианты, ограничения. По шагу на каждое, с кодом, который пишешь ты.

Первые 33 шага бесплатные, и все пять вещей внутри них.

Навык поверх этих пяти это распознавание паттернов. Спутанные пары перечислены в статье какие паттерны путают.

Если материал не столько сложный, сколько неприятный, это другая проблема с другим лечением.