알고리즘 정리 (3) 썸네일형 리스트형 KMP 알고리즘 참고 블로그: https://pearlluck.tistory.com/581 [python] 문자열매칭. KMP 알고리즘 (백준16916, 백준1786) 단어검색 (문자열매칭) 요구사항 - 워드안에서 Ctrl+F하는 것 처럼, 검색한 단어들이 있는 모든 위치를 전부 알려줘! - 단어사전에 단어가 수만개, 문서길이가 수천개 - 문서는 띄어쓰기가 없거나 pearlluck.tistory.com KMP 알고리즘을 이해하는데 위 블로그를 참고했다. 한 문자열 M이 다른 문자열 N이랑 매치되거나 포함되는지 확인하는 알고리즘으로 쉽게 생각해볼 수 있는건 N에서 M의 시작점을 옮겨가며 매치되는지 확인하는 것이다. 하지만 이와 같은 방법으로는 O(MN)의 시간복잡도를 가진다. KMP 알고리즘을 사용하면 접두사와 접미사가 .. 위상정렬 알고리즘 참고 블로그: https://velog.io/@younge/Python-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 [Python] 그래프 - 위상 정렬(Topology Sort) 알고리즘 구현하기 다음과 같은 조건을 가진 그래프라면 위상 정렬을 할 수 있다. 간선이 방향성을 가진 그래프여야 한다. 그래프 내부에 순환(Cycle)이 없어야 한다. 즉, 위상 정렬은 DAG(Direct Acyclic Graph)에 대해서만 velog.io 한마디로 "1을 하기 전에는 2를 할 수가 없다." 라는 일정한 순서가 정해져 있을 때 쓰기 편한 알고리즘이라고 한다. 위상정렬의 s.. 벨만포드 알고리즘 https://yabmoons.tistory.com/365 [ 벨만포드 알고리즘 ] 개념과 구현방법 (C++) 이번 글에서는 벨만포드 알고리즘에 대해서 알아보자. 1. 벨만포드 알고리즘 ?? 그래프 알고리즘에서 '최소비용'을 구하는 대표적인 알고리즘으로는 '다익스트라 알고리즘', '벨만포드 알고리즘' yabmoons.tistory.com 위 블로그를 참고해서 이해했다. 왼쪽에서부터 오른쪽, 위에서 밑으로 벨만포드의 진행 과정을 4단계까지 진행해보았다. 첫번째 노드의 dist를 0으로 초기화하고 모든 간선들을 다 순회한다. 시작 노드의 dist가 무한대가 아니면 그 노드를 거쳐가는게 더 짧은지 계산해본다. V-1만큼 돌리고 한번 더 벨만포드 알고리즘을 돌려서 최소비용이 변하는 노드가 있으면 음의 사이클이 .. 이전 1 다음
