본문 바로가기

알고리즘15

플로이드-워셜 알고리즘 📌 플로이드-워셜 알고리즘 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 특정 시작점, 도착점을 가지는 경로의 최소 비용을 구할 때 양의 가중치에서는 다익스트라 알고리즘, 음의 가중치에선 벨만-포드 알고리즘을 사용하여 구할 수 있었다. 플로이드-워셜은 특정 지점이 아닌 그래프의 모든 노드 쌍에서 최단 거리를 구할 때 사용할 수 있다. 항상 최소 비용의 노드를 먼저 선택했던 다익스트라 알고리즘(PriorityQueue)과는 다르게 플로이드-워셜 알고리즘은 거쳐가는 간선의 비용과 직행하는 간선의 비용을 비교해본다. 다음과 같은 그래프가 존재한다고 했을 때 C와 A+B 중 최소 비용으로 갈 수 있는지를 구하면 된.. 2022. 10. 19.
벨만-포드 알고리즘 📌 벨만-포드 알고리즘 벨만-포드(Bellman-Ford) 알고리즘은 그래프가 가중치를 가지는 방향있는 변(Edge)으로 이루어져 있을때 한 점(Vertex)에서 나머지 다른 점까지의 최단 경로를 찾는 알고리즘이다. 목표만 봤을 때 다익스트라 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 그러면 뭐가 다르냐? 바로 음의 가중치에 대해서도 최단 경로를 구할 수 있다. 앞서 다익스트라 알고리즘을 설명할 때 양의 가중치에서만 해당 알고리즘을 사용한다고 했었는데, 음의 가중치에서 다익스트라 알고리즘을 사용할 수 없는 이유는 다음과 같다. 음의 가중치 무한 순환 다음과 같은 노드가 있을 때 4번 노드로 가는 최단 경로는 1 -> 2 -> 3 -> 4이 될 것이다. 그런데 다익스트라 알고리즘 특성상 가장 작은 .. 2022. 10. 13.
다익스트라 알고리즘 📌 다익스트라 알고리즘 다익스트라(Dijkstra) 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘을 말한다. 다익스트라 알고리즘은 dp와 그리디 알고리즘을 활용해 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 활용한 알고리즘이 고안돼 현재는 O(V+E)log V)의 시간복잡도를 가지고 있다. (연결 그래프의 경우 O(ElogV)) 해당 글에서는 우선순위 큐를 활용한 다익스트라 알고리즘에 대해 소개하고자 한다. 초기 설정 1. 비용에 대해 정렬하기 위한 노드를 구현한다. // 비용에 대한 정렬을 위해 Comparable을 구현 public static class Node implements Comparable { pu.. 2022. 10. 11.
최장 증가 부분 수열 - LIS 📌 LIS LIS는 Longest increasing subsequence의 줄임말으로 증가하는 가장 긴 수열의 길이를 찾는 알고리즘이다. [10, 20, 10, 30, 20, 50]의 배열에서 가장 긴 증가 수열을 구하자면 [10, 20, 10, 30, 20, 50]으로 길이는 4가 된다. 이와 같이 배열 내에 가장 긴 증가 수열을 구하는 알고리즘을 LIS라고 한다. ✔️ DP - O(N^2) DP로 LIS를 풀기 전 점화식을 먼저 도출해야한다. DP의 점화식은 다음과 같다. dp[i] = Max(dp[i], dp[j]+1) 해당 관계식을 살펴보자. 주황색으로 칠해진 5에서의 dpArr(최대 길이)의 값을 구한다고 생각해보자. 5의 위치 전까지 dpArr이 어찌저찌해서 만들 수 있는 최대 길이가 채워졌.. 2022. 8. 31.

티스토리툴바