개발일지

개념 Floyd Warshall (플로이드 와샬) 알고리즘은 정점과 정점 사이의 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 특징은 모든 정점 사이의 거리를 구할 수 있다. 최단 경로를 찾을 때 중간에 한번 거쳐서 가는 경로 중 가장 가까운 경로로 업데이트 하면서 모든 정검들의 최단 거리를 구하는 알고리즘이다. 시간 복잡도가 O(V^3)이라는 꽤 오래 걸리는 알고리즘 이지만 모든 정점 사이의 최단 거리를 구할 수 있다. 작동원리 1. 중간 정점 K, 시작 정점 I, 도착 정점 J로 삼중 반복문을 순회한다. 2. distance[i][j]가 distance[i][k] + distance[k][j]보다 크면 경로를 업데이트 한다. -> distance[i][k], distance[k][j]가 ..

개념 Short Path Faster Algorithm의 약어로 가장 빠른 경로를 찾는 알고리즘이다. 다익스트라 알고리즘은 음수인 간선이 존재할 때 사용할 수 없고, 벨만-포드 알고리즘보다 효율이 좋기 때문에 MCMF 알고리즘에서 많이 사용한다. 작동원리 isIn => 덱에 해당 정점이 있는지 확인하는 배열, 큐에 중복으로 값을 넣는 것을 방지 count => 업데이트된 횟수를 저장하는 배열, CYCLE을 확인할 수 있다.(벨만-포드와 같은 개념) 1. 시작 정점을 덱에 넣고 count, isIn, distance를 업데이트한다. 2. 덱에서 POP FRONT하고 isIn을 false로 업데이트한다. 3. 현재 정점에서 갈 수 있는 정점중 distance를 업데이트 할 수 있는 정점이 있으면 distan..

개념 최단거리를 구하는 알고리즘이다. 최단거리 + 최단거리 = 최단거리라는 그리디한 개념으로 최단거리를 찾는다. => 간선의 가중치가 음수인게 존재하면 다익스트라를 사용할 수 없다. (최단거리 + 최단거리 = 최단거리라는 보장이 깨지기 때문에) 작동원리 1. 시작 노드를 우선순위 큐에 넣는다. 2. 우선순위 큐에서 POP을한다. 3. POP한 노드가 최단거리이면 해당 노드에서 갈 수 있는 노드중 거리를 갱신하는 노드를 우선순위 큐에 PUSH한다. 4. 2 ~ 3을 우선순위 큐가 EMPTY가 될 때까지 한복한다. 시간복잡도 O(ElogV) 문제 11779 최소비용 구하기 2 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)..