기록보관소

벨만-포드 알고리즘 벨만-포드 알고리즘은 가중치를 가지는 방향그래프의 최단거리를 구하는 데 사용되는 알고리즘입니다. 특징으로 음의 가중치를 가지는 경우에도 사용할 수 있습니다. 또한 출발점에서 도달가능한 음의 순환의 존재 여부를 확인할 수도 있습니다. 음의 순환이 존재하면 최단거리는 구할 수 없습니다. 모든 최단경로는 순환을 가지지 않으며 따라서 한 정점을 두 번 이상 방문하지 않습니다. 그래프에 정점이 V개 있다면 최단 경로는 최대 V-1개의 간선을 가질 수 있습니다. 최단거리 계산에는 출발점에서 도착점까지의 경로를 순서대로 완화함으로써 최단거리 값을 구할 수 있다는 정리가 이용됩니다. 그래프의 모든 간선을 V-1번 완화(노드의 추정최단거리 값을 갱신하는 행위)하면 한 출발점에서의 모든 다른 노드까지로..

스타트링크 문제는 BFS를 사용하여 해결할 수 있는 문제입니다. 시작 층을 하나의 노드로, 도착 층을 하나의 노드로 생각하고 U, D 버튼을 다른 노드로 가는 간선을 나타낸다고 생각하면 BFS로 생각할 수 있습니다. 최소한으로 버튼을 눌러서 도착하기 위해서는 BFS를 사용하여 U, D 버튼으로 이동가능한 모든 노드를 탐색해야 합니다. BFS에 대한 설명은 다음의 게시물에서 확인할 수 있습니다. 2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS와 BFS에 대한 충실한 이해가 필요합니다. DFS의 경우 처음 발..

미로 탐색 문제는 노드 사이의 최단 거리를 구하는 문제이다. 노드 간 최단 거리를 구할 때는 BFS를 사용할 수 있다. BFS 알고리즘 특성상 그래프에서 노드간 최단 거리를 찾기 때문이다. BFS의 일반형에서 약간의 변형을 통해 코드를 구현할 수 있다. BFS 일반형은 다음 게시물에서 참고할 수 있다. 2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS와 BFS에 대한 충실한 이해가 필요합니다. DFS의 경우 처음 발견된 노드를 기준으로 그 노드에 연결된 노드들을 탐색(DFS)를 ark-hive.tistory..