DFS (Depth-First Search) или поиск в глубину
Основные применения метода поиска в глубину:
- Обнаружение компонента связанности в графе (связи в неориентированных графах)
- Проверка наличия циклов
- Топологическая сортировка
- Поиск путей
- Решение задач на генерацию лабиринтов, перестановок и комбинаций
- Решение задач на поиск оптимальной стратегии
Алгоритм:
1. Начинаем с определения начальной вершины.
2. Помещаем начальную вершину в стек и отмечфем ее как посещенную.
3. Пока стек не пуст, извлекаем вершину из стека.
4. Проверяем всех соседей текущей вершины. Если сосед еще не был посещен, помещаем его в стек и отмечаем как посещенный.
5. Повторяйте этот процесс, пока не будет достигнута конечная вершина или пока не будут исследованы все доступные ветви.
Временная сложность: O(V + E)
- V — количество вершин (узлов) в графе.
- E — количество рёбер (или связей) в графе.
Пространственная сложность: O(V)
Пример: Найти путь от начальной вершины до целевой вершины в графе.
Основные применения метода поиска в глубину:
- Обнаружение компонента связанности в графе (связи в неориентированных графах)
- Проверка наличия циклов
- Топологическая сортировка
- Поиск путей
- Решение задач на генерацию лабиринтов, перестановок и комбинаций
- Решение задач на поиск оптимальной стратегии
Алгоритм:
1. Начинаем с определения начальной вершины.
2. Помещаем начальную вершину в стек и отмечфем ее как посещенную.
3. Пока стек не пуст, извлекаем вершину из стека.
4. Проверяем всех соседей текущей вершины. Если сосед еще не был посещен, помещаем его в стек и отмечаем как посещенный.
5. Повторяйте этот процесс, пока не будет достигнута конечная вершина или пока не будут исследованы все доступные ветви.
Временная сложность: O(V + E)
- V — количество вершин (узлов) в графе.
- E — количество рёбер (или связей) в графе.
Пространственная сложность: O(V)
Пример: Найти путь от начальной вершины до целевой вершины в графе.
package main
import (
"fmt"
)
type Graph struct {
Nodes map[string][]string
}
func NewGraph() *Graph {
return &Graph{
Nodes: make(map[string][]string),
}
}
func (g *Graph) AddEdge(src, dest string) {
g.Nodes[src] = append(g.Nodes[src], dest)
g.Nodes[dest] = append(g.Nodes[dest], src) // для ненаправленного графа
}
func DepthFirstSearch(graph *Graph, start, target string) []string {
visited := make(map[string]bool)
stack := []string{start}
visited[start] = true
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if node == target {
return stack // Возвращаем стек, содержащий путь от начальной до целевой вершины
}
for _, neighbor := range graph.Nodes[node] {
if !visited[neighbor] {
stack = append(stack, neighbor)
visited[neighbor] = true
}
}
}
return nil // Целевая вершина не достижима
}
Когда-нибудь алгосы начнут собирать больше просмотров. Наверно, тогда, когда вы начнете готовиться к собесам. Потому что недавно обсуждали с коллегой, что степень знания алгоритмов прямо пропорциональна близостью к собеседованию и обратно пропорциональна выходу на работу.
Ну, а пока вы думаете над первым абзацем, закину вам крутую статью. Если кто ожидает увидеть там что-то на IT-шном - я вас расстрою. Это публикация про мою свадьбу. Все самое интересное от подготовки до мероприятия глазами жены ❤️
Статья на Weddywood
Ну, а пока вы думаете над первым абзацем, закину вам крутую статью. Если кто ожидает увидеть там что-то на IT-шном - я вас расстрою. Это публикация про мою свадьбу. Все самое интересное от подготовки до мероприятия глазами жены ❤️
Статья на Weddywood
Weddywood
It's a fire: лёгкая вечеринка с символичной концепцией
Тот самый момент, когда огонёчки в сторис стали счастливым и долгим началом истории Артёма и Люси. Смотрим стильный и классный праздник ребят!
🥰5🔥3❤2
Очень надоело одно и тоже музло в Яндекс.музыке, но заморачиваться со спотиком лень🦥
ВК музыка вносит немного разнообразия, но вау эффекта нет. Огромный плюс, что там есть миксы от знакомых мне DJ, которые мне нравится слушать.
В связи с этим, стало интересно, а что слушаешь ты? Кидай трек, который пришел в голову в комменты. Хоть так внесу какое-то разнообразие и сломаю свою подборку Яндекс музыки.
Ну и фото кошечки вам, у нее сегодня праздник, поэтому поставьте лайк этой сладкой булочке.
ВК музыка вносит немного разнообразия, но вау эффекта нет. Огромный плюс, что там есть миксы от знакомых мне DJ, которые мне нравится слушать.
В связи с этим, стало интересно, а что слушаешь ты? Кидай трек, который пришел в голову в комменты. Хоть так внесу какое-то разнообразие и сломаю свою подборку Яндекс музыки.
Ну и фото кошечки вам, у нее сегодня праздник, поэтому поставьте лайк этой сладкой булочке.
🔥2💘1
This media is not supported in your browser
VIEW IN TELEGRAM
Вчера была «пятничная» встреча во ВКонтакте. Прикольное мероприятие, на котором рассказывают, каких успехов мы достигли по истечению N-го времени и к чему стремимся. Еще можно задать вопрос, который тебя долго мучал. В сухом остатке, конечно, это цифры, графики и отчеты, но компания всегда пытается сделать это максимально прикольно.
Например вчера на этой встрече был тайный гость, которого не показывали до начала. Нурлан Сабуров прикольно вписался, хотя и моментами смотрелось глупо. Мое мнение - эксперимент удался. Информация действительно воспринималась проще, ну и подколы от Нурлана делали свое дело.
Прозрачные процессы в компании - это шикарно. Я за открытость. В такой атмосфере ты не чувствуешь себя лишним и от этого даже работать как-то приятнее
Например вчера на этой встрече был тайный гость, которого не показывали до начала. Нурлан Сабуров прикольно вписался, хотя и моментами смотрелось глупо. Мое мнение - эксперимент удался. Информация действительно воспринималась проще, ну и подколы от Нурлана делали свое дело.
Прозрачные процессы в компании - это шикарно. Я за открытость. В такой атмосфере ты не чувствуешь себя лишним и от этого даже работать как-то приятнее
🔥4❤2🐳1
Цель поставлена, и я иду к ней.
Я очень давно хотел выступить на крупных конференциях по типу Highload. И сегодня я стал еще немного ближе к этому.
Я прошел первый этап защиты темы доклада на GolangConf.
Кстати, защищал перед Данилом Подольским, с которым разбирали резюме go-разработчиков
Посмотреть на YouTube
Я очень давно хотел выступить на крупных конференциях по типу Highload. И сегодня я стал еще немного ближе к этому.
Я прошел первый этап защиты темы доклада на GolangConf.
Кстати, защищал перед Данилом Подольским, с которым разбирали резюме go-разработчиков
Посмотреть на YouTube
cfp.golangconf.ru
GolangConf 2026
Подайте доклад на профессиональную конференцию для Go-разработчиков
❤6🔥2
В канале 70 человек. Честно говоря, я рад каждому, а еще круто, что большая часть людей это не мой список контактов.
Я сейчас собираю материал на первый видос, который я давно хотел записать. Вообще, я его уже собрал по большей части. Но вот записать не решаюсь. Причина супер простая: я хочу делать сразу круто.
Для меня важна картинка, качество звука, точность материала. Если я сделаю иначе, то мой внутренний голос, мне кажется, сожрет меня, и я удалю видос через минуту публикации.
К чему я это все? Мне стало интересно, что на твой взгляд важнее: материал или картинка(продакшн)?
P.S. Опросы в канале на 70 человек делать не очень эффективно, это я уже проверил. Но все же попробую.
Я сейчас собираю материал на первый видос, который я давно хотел записать. Вообще, я его уже собрал по большей части. Но вот записать не решаюсь. Причина супер простая: я хочу делать сразу круто.
Для меня важна картинка, качество звука, точность материала. Если я сделаю иначе, то мой внутренний голос, мне кажется, сожрет меня, и я удалю видос через минуту публикации.
К чему я это все? Мне стало интересно, что на твой взгляд важнее: материал или картинка(продакшн)?
P.S. Опросы в канале на 70 человек делать не очень эффективно, это я уже проверил. Но все же попробую.
🔥6❤4👍1💅1
Миньоны - топ. Я не знаю, зачем это скрывали от нас столько времени…
Никогда не задумывался, как их озвучивают. Но если бы до этого меня спросили, знаю ли я, как это делают, то первая мысль, которая пришла бы в голову, - просто играют с частотами голоса какого-то актера дубляжа.
Я долгое время занимался музыкой. Работал в ДК звукорежиссером, играл DJ на мероприятиях, сводил треки, и поэтому для меня это был бы самый очевидный и простой вариант. Но все оказывается еще проще и круче
Никогда не задумывался, как их озвучивают. Но если бы до этого меня спросили, знаю ли я, как это делают, то первая мысль, которая пришла бы в голову, - просто играют с частотами голоса какого-то актера дубляжа.
Я долгое время занимался музыкой. Работал в ДК звукорежиссером, играл DJ на мероприятиях, сводил треки, и поэтому для меня это был бы самый очевидный и простой вариант. Но все оказывается еще проще и круче
🔥8😍1
На очереди ухода из России Miro.
Стал все чаще задумываться о том, что надо поставить себе новый роутер и накатить на него VPN на определенные адреса. Дико надоедает включать/выключать его постоянно.
Но наши ребята прикольно подхватили это дело и напилили новый сервис "VK доска". Пост не рекламный, денег за него мне не дадут, поэтому скажу как есть.
Функционал скудный, фич мало, но для какой-то простой блок схемы, плана работы или заметок подойдет. Сама по себе доска работает шустро, плавно. Ребята постарались. Сейчас идет активный набор к ним в команду, думаю, сделают конфетку, и будем все на VK досках рисовать.
P.S. Если вдруг интересно, то могу вакансию скинуть. У них там Go, gRPC, PostgreSQL, Docker, Kubernetes, Node.js, Redis.
Стал все чаще задумываться о том, что надо поставить себе новый роутер и накатить на него VPN на определенные адреса. Дико надоедает включать/выключать его постоянно.
Но наши ребята прикольно подхватили это дело и напилили новый сервис "VK доска". Пост не рекламный, денег за него мне не дадут, поэтому скажу как есть.
Функционал скудный, фич мало, но для какой-то простой блок схемы, плана работы или заметок подойдет. Сама по себе доска работает шустро, плавно. Ребята постарались. Сейчас идет активный набор к ним в команду, думаю, сделают конфетку, и будем все на VK досках рисовать.
P.S. Если вдруг интересно, то могу вакансию скинуть. У них там Go, gRPC, PostgreSQL, Docker, Kubernetes, Node.js, Redis.
3🔥4
Сложная неделька выдалась. А она еще и не закончилась…
Не успеваю ничего писать в канал от слова совсем.
Вчера с Вовой Балун записали еще один подкаст, обсудили. что нового произошло за год.
Если не видели предыдущий выпуск, то бегом смотреть - самый дорогой it-ментор
На фото еще наш супер крутой режиссер монтажа Наташа. Если ищете себе такого юнита в команду, поделюсь контактом
Не успеваю ничего писать в канал от слова совсем.
Вчера с Вовой Балун записали еще один подкаст, обсудили. что нового произошло за год.
Если не видели предыдущий выпуск, то бегом смотреть - самый дорогой it-ментор
На фото еще наш супер крутой режиссер монтажа Наташа. Если ищете себе такого юнита в команду, поделюсь контактом
1🔥6❤2🥰1
Вчера был тимбилдинг технического департамента ВКонтакте
Крутая движуха. Могла бы быть, но погода внесла свои коррективы, и получилось как получилось.
Много активностей, еды, напитков, музыки. В общем, было круто с парочкой «но».
Все это перекрыло знакомство с новой командой. Очень круто общаться в реале, а не только в зум звонке.
Крутая движуха. Могла бы быть, но погода внесла свои коррективы, и получилось как получилось.
Много активностей, еды, напитков, музыки. В общем, было круто с парочкой «но».
Все это перекрыло знакомство с новой командой. Очень круто общаться в реале, а не только в зум звонке.
2❤1🔥1
This media is not supported in your browser
VIEW IN TELEGRAM
Давно ничего не писал сюда.
За это время множество новостей произошло в мире, но другие каналы справились с задачей вам это все рассказать. Особо не было интереса говорить про это все)
А у меня новостей особо и нет, я вот руку покрасил, что бы это не значило. Вспомнил времена, когда красил одну из своих первых машин в гараже, даже нашел объявление о ее продаже на avito (ставь реакцию глаз если тоже интересно посмотреть).
А еще готовлюсь 4 сентября провести лекции в ИТМО. 1 день 5 лекций, это будет интересно. Подобной практики у меня еще не было, но времена универа - это кайф (может как-нибудь расскажу и покажу, чем занимался в универе)
За это время множество новостей произошло в мире, но другие каналы справились с задачей вам это все рассказать. Особо не было интереса говорить про это все)
А у меня новостей особо и нет, я вот руку покрасил, что бы это не значило. Вспомнил времена, когда красил одну из своих первых машин в гараже, даже нашел объявление о ее продаже на avito (ставь реакцию глаз если тоже интересно посмотреть).
А еще готовлюсь 4 сентября провести лекции в ИТМО. 1 день 5 лекций, это будет интересно. Подобной практики у меня еще не было, но времена универа - это кайф (может как-нибудь расскажу и покажу, чем занимался в универе)
2👀6👍3❤🔥2
Люблю вписываться в различные проекты. Как раз один из таких сейчас на финишной прямой, и у него интересная история.
Я делаю его для студии Sound Partner, с владельцем которой я познакомился еще лет 5 назад, когда только переехал в Питер. После небольшого общения-собеседования мы очень быстро нашли коннект, и меня начали ставить играть в заведения Питера.
Но со временем играть я перестал и пошел заниматься web-разработкой (а то что, зря учился что ли). И вот, спустя 4 года, мы снова выходим на контакт и договариваемся о реализации масштабного проекта. Вот он нетворкинг в действии.
В проекте сошлось все, очередной тотальный мэтч. Я люблю заниматься разработкой и делать что-то новое и крутое, также моя любовь к музыке никуда не делась, а заказчик знает мой ответственный подход к работе и мое погружение в предметную область.
Пара встреч, небольшое обсуждение, составление ТЗ, дизайн, и вот мы бросаем все силы на запуск проекта, о котором расскажу чуть позже, а может вообще запишем подкаст с владельцем студии
Я делаю его для студии Sound Partner, с владельцем которой я познакомился еще лет 5 назад, когда только переехал в Питер. После небольшого общения-собеседования мы очень быстро нашли коннект, и меня начали ставить играть в заведения Питера.
Но со временем играть я перестал и пошел заниматься web-разработкой (а то что, зря учился что ли). И вот, спустя 4 года, мы снова выходим на контакт и договариваемся о реализации масштабного проекта. Вот он нетворкинг в действии.
В проекте сошлось все, очередной тотальный мэтч. Я люблю заниматься разработкой и делать что-то новое и крутое, также моя любовь к музыке никуда не делась, а заказчик знает мой ответственный подход к работе и мое погружение в предметную область.
Пара встреч, небольшое обсуждение, составление ТЗ, дизайн, и вот мы бросаем все силы на запуск проекта, о котором расскажу чуть позже, а может вообще запишем подкаст с владельцем студии
2🔥9❤3
6 лекций подряд было не просто смело, было очень смело. Спасибо всем, кто тратил на нас время в универе, я понял как это тяжело🫠
Но в целом, мне понравилось. Крутой вуз, огромное количество заряженных ребят. Атмосфера, которая вернула меня во времена моей учебы
Чуть позже я расскажу больше, а сейчас я устал и хочу есть
Но в целом, мне понравилось. Крутой вуз, огромное количество заряженных ребят. Атмосфера, которая вернула меня во времена моей учебы
Чуть позже я расскажу больше, а сейчас я устал и хочу есть
1🔥12
Всё, собрался, пишу пост про недавнюю активность в универе.
Первое, что хочу сказать: для меня университетское время — это период, в который я бы с большим удовольствием вернулся. Поэтому на всех лекциях я советовал прожить университетскую жизнь на максимум, потому что потом такого шанса не будет.
В ИТМО очень круто. Я не во многих вузах нашей страны бывал, и в основном сравниваю с тем, где учился я, и здесь разница огромная:
* Коворкинги
* Техническое оснащение
* Автоматы с кофе на каждом шагу
* Всевозможные коллаборации с крупнейшими технологическими компаниями страны
* Собственный технопарк
Это лишь те вещи, которые я отметил для себя, поднявшись на третий этаж… Для сравнения, наш коворкинг был либо столовая, либо свободный кабинет, в который еще не пришла группа или преподаватель.
Теперь о самих лекциях. Шесть лекций подряд — это тяжело. В общей сложности меня послушали порядка 100+ человек, в основном это первокурсники, но радует, что почти все ребята пришли в профессию, потому что им это нравится.
Я рассказывал о том, какие направления сейчас есть в IT и как выбрать своё, как проходить собеседования и на что обращают внимание, дал немного советов как профессиональные так и жизненные и ответил на вопросы. Моя коллега рассказала о том, как можно быстро, без СМС и регистрации попасть в ВКонтакте на стажировки или курсы.
И вот так шесть раз подряд… Но все равно это классный опыт, мне понравилось, и я с удовольствием пойду ещё.
Первое, что хочу сказать: для меня университетское время — это период, в который я бы с большим удовольствием вернулся. Поэтому на всех лекциях я советовал прожить университетскую жизнь на максимум, потому что потом такого шанса не будет.
В ИТМО очень круто. Я не во многих вузах нашей страны бывал, и в основном сравниваю с тем, где учился я, и здесь разница огромная:
* Коворкинги
* Техническое оснащение
* Автоматы с кофе на каждом шагу
* Всевозможные коллаборации с крупнейшими технологическими компаниями страны
* Собственный технопарк
Это лишь те вещи, которые я отметил для себя, поднявшись на третий этаж… Для сравнения, наш коворкинг был либо столовая, либо свободный кабинет, в который еще не пришла группа или преподаватель.
Теперь о самих лекциях. Шесть лекций подряд — это тяжело. В общей сложности меня послушали порядка 100+ человек, в основном это первокурсники, но радует, что почти все ребята пришли в профессию, потому что им это нравится.
Я рассказывал о том, какие направления сейчас есть в IT и как выбрать своё, как проходить собеседования и на что обращают внимание, дал немного советов как профессиональные так и жизненные и ответил на вопросы. Моя коллега рассказала о том, как можно быстро, без СМС и регистрации попасть в ВКонтакте на стажировки или курсы.
И вот так шесть раз подряд… Но все равно это классный опыт, мне понравилось, и я с удовольствием пойду ещё.
1❤13🔥2