-
python으로 구현한 다익스트라 알고리즘(dijkstra)
다익스트라 알고리즘 인접 행렬 그래프와 시작 정점이 주어졌을 때, 다익스트라 알고리즘을 사용하면 시작 정점에서 모든 정점으로 가는 최단 거리를 구할 수 있게 됩니다. 여기서는 인접행렬을 사용해 구현했습니다. 구현에 대한 상세한 내용은 아래 구현 소스 부분에 아주 상세하게 주석을 달아놓았습니다. 복잡도 시간복잡도는 최악의 경우 모든 노드를 방문하는데 V, 방문 할 때마다...
-
(ALGO) 백준 1561번 문제 - 놀이공원 문제(python)
백준 1561번 문제 해설 이분 탐색을 살짝 응용한 문제다. N이 20억이기 때문에 N을 이용하려면 logN의 속도로 처리해야 하기 때문에, 이분 탐색이 적절할 것이라고 생각하면 될 것 같다. 놀이기구와 타는 애들과의 관계를 표로 잘 정리하면, 특정 시간 n(소스 코드에선 mid가 해당됨)에 애들을 여태까지 몇 명 태웠는지를 계산 할 수 있다. 이...
-
(ALGO) 백준 2294번 문제 - 동전 2 문제(C++)
다이나믹 프로그래밍(Dynamic Programming, DP) 문제이다. 절차 가장 먼저 우리가 구하고자 하는 해답 함수를 정의한다. coin(n, k) 함수의 정의 : n번째 동전부터 마지막 동전(N-1번째 동전)을 가지고 k를 만들 수 있는 최소 경우의 수. 즉, 해답은 coin(0,K)가 된다. 해답 함수에 대한 점화식을 정의한다. 점화식: coin(n,k) = min(coin(n+1, k), coin(n, k-cost[n])+1) 자세한 설명은...
-
(ALGO) 백준 9663번 문제 - N-Queen 문제(C++)
Backtracking(가지 치기) 문제로 유명한 N-Queen 문제이다. Backtracking이란, 간단하게 말해 brute-force(전부 일일히 다 해보는 것)방법을 수행하지만 한정 함수(bounding function)을 이용해 경우의 수를 줄여나가는 방법을 말한다. 아래는 백트래킹에서 Bounding function(아래 코드에선 promising 함수)를 사용해 구현한 것이다. 시간복잡도는 O(N^N)이어야 하지만, 한정 함수에 의해 실제로는 더 빠른 속도로 수행되는 것을 알 수 있다. #include...
-
다단계 그래프(Multistage Graph) 구현
import java.io.BufferedReader; import java.io.FileReader; import java.util.Scanner; public class MultistageGraph { private static Scanner scanner = new Scanner(System.in); // for input private static int[][] graph; // 인접행렬로 표현한 그래프 private static int[][] d; // 최소 비용 경로 private static int numOfVertices, numOfEdges; // 정점 개수, 간선 개수 // 최소 비용 및...