ImJay

[파이썬/Python] 최단 경로 알고리즘 작동원리 이해하기 ( Dijkstra ) 서론 [파이썬/Python] 최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall ) 최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall ) 서론 최단 경로(Shortest Paths)는 두 정점 사이의 경로를 구성하는 모든 간선의 가중치 합이 최소인 경로를 말합니다. 최단 경.. develop247.tistory.com 이전 시간 구현하였던 Dijkstra 알고리즘의 작동원리에 대해 간단한 예제를 통해 그림으로 이해해보려고 합니다. 본론 문제 1. Dijkstra 알고리즘을 이용하여 위 그래프의 v4를 시작으로 하는..

최소 비용 신장 트리 알고리즘 작동원리 이해하기 ( Prim / Kruskal ) 서론 [파이썬/Python] 최소 비용 신장 트리 알고리즘 구현하기 ( Prim / Kruskal ) 최소 비용 신장 트리 알고리즘 구현하기 서론 신장 트리(Spanning tree)란 연결된 비방향성 그래프에서, 노드는 그대로 유지한 채로, 순환경로(cycle)가 없어지도록 이음선을 제거하여 구성한 연결된 develop247.tistory.com 이전 시간 구현하였던 Prim, Kruskal 알고리즘의 작동원리에 대해 간단한 예제를 통해 그림으로 이해해보려고 합니다. 본론 문제 1. Prim 알고리즘을 이용하여 위 그래프의 최소비용 신장 트리를 구하는 과정을 제시하시오. 처음 start_node = 1이므로, d[1] =..

동적 프로그래밍 - 행렬 곱셈 순서 계산하기 ( Brute-Force Algorithm ) 서론 동적 프로그래밍(Dynamic Programming)은 최적 부분 구조(Optimal Substructure)를 가지고 있고, 재귀 호출 시 비효율적인 중복이 발생하는 경우(Overlapping Recursive Calls) 사용하면 효과적이다. 최적 부분 구조(Optimal Substructure)란 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함되는 것을 말한다. 동적 프로그래밍을 적용하기 위해 항상 최적 부분 구조를 갖고 있는지 먼저 확인해야 한다. 그렇다면, 대표적인 동적 프로그래밍 문제로 행렬 곱셈 순서에 대해 동적 프로그래밍을 적용해보자. 본론 i × j 행렬과 j × 행렬을 곱하기 위해서..