algorithm
1.개선된 다익스트라(dijkstra) 알고리즘 소스코드(with Python) - 최단 경로 알고리즘
다익스트라 알고리즘은 '단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'한 뒤에, 그 노드를 거쳐 가는 경우를 확인하여 최단 거리를 갱신하는 방법이다. 우선순위 큐를 이용하여 소스코드를 작성할 수 있다는 점을 기억해야한다.개선된 다익스트라 알고리
2.플로이드 워셜(Floyd-Warshall) 알고리즘 (with Python) - 최단 경로 알고리즘
플로이드 워셜 알고리즘'모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 알고s리즘이다. 다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용했다. 반면에 플로이드
3.우선순위 큐(with Python)
파이썬에서는 힙(heap)기능을 위해 heapq 라이브러리를 제공한다. heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다. heapq 외에도 PriorityQueue 라이브러리를 사용할 수 있다. 하지
4.다양한 그래프(Graph) 알고리즘
그래프(graph)란 노드(node)와 노드 사이에 연결된 간선(edge)의 정보를 가지고 있는 자료구조를 의미한다. 알고리즘 문제를 접했을 때 '서로 다른 개체(혹은 객체)가 연결되어 있다.'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 예를 들어
5.신장 트리(Spanning Tree)(크루스칼 알고리즘(Kruskal))(with Python)
신장 트리는 그래프 알고리즘 문제로 자주 출제되는 문제 유형이다. 기본적으로 신장 트리란 하나의 그래프가 있을 떄 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의
6.위상 정렬(Topology Sort)(with Python)
위상 정렬(Topology Sort)은 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 위상 정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다.위상
7.DFS(Depth-First Search)(with Python)
DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색해야하는 알고리즘이다.