Notion - 다익스트라 이번에는 다익스트라에 대해 정리하고, 문제를 기준으로 이해해보자. https://www.acmicpc.net/problem/1916 - 최소비용 구하기 / Gold 5 위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.581 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 31 5다익스트라 알고리즘?다익스트라는 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.다익스트라는 2중 for문을 이용한 방법, 우선순위 큐를 이용한 탐색으로 구현 방법이 나뉜다.그럼 이번에도 그림으로 표현해보도록 하겠다. 이전 글인 플로이드 워셜과 유사하게 접근이 가능하다.INF를 사용하지만 이번에는 시작 지점만을 위한 가중치 배열인 dist를 따로 선언하여 사..
Notion - 플로이드 워셜 이번에는 플로이드 워셜에 대해서 정리하고, 문제를 기준으로 이해해보자. https://www.acmicpc.net/problem/11404 - 플로이드 / Gold 4 위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.5141 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 33 5 103 1 81 4 25 1 73 4 25 2 4플로이드 워셜 알고리즘?플로이드 워셜은 모든 노드 간의 최단경로를 구할 때 사용되는 알고리즘이다.플로이드 워셜 3중 for문을 이용해서 구현할 수 있다. 우선 예제를 기준으로 표현해보자면 아래와 같다. 예제에서 나온 중복되는 경로에서의 큰 값은 제외하고 인접행렬을 만들었을 때 오른쪽과 같이 만들어 낼 수 있다.여기서 I..
Notion - DFS와 BFS DFS와 BFS에 대해서와 인접 행렬과 인접 그래프에 대해서 정리하고, 한 문제를 통해서 이해해보자.설명에 앞서 코드에 대한 기준을 정하고 시작하면 좋을 것 같아 아래 문제를 기준으로 설명하도록 하겠다. https://www.acmicpc.net/problem/1260 - DFS와 BFS / Silver 2 위 문제의 예제 1번인 아래 입력을 기준으로 설명하도록 하겠다.4 5 11 21 31 42 43 4DFS (Depth-First Search)DFS는 깊이 우선 탐색이라고 부르며, 깊은 부분부터 우선적으로 탐색하는 알고리즘이다.DFS는 Stack 자료구조 혹은 재귀 함수를 이용하여 구현할 수 있다. DFS로 위 예제를 탐색하게 되면 1 2 4 3 이라는 결과를 얻을 수..
