전체 글 (92) 썸네일형 리스트형 [Algorithm 기초] 최단 경로 알고리즘 (벨만 포드) 벨만-포드(Bellman-Ford) - 음수 간선이 포함되어 있어도 최단 경로 구할 수 있음. 단 음수 사이클이 있으면 정상 동작하지 않음 - 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림 알고리즘 복잡도 : O(VE) import java.util.ArrayList; //벨만포드 - 기본 사용방법 (매번 최소 간선을 구하기 위해서 구하는 구현) public class bellmanFord { static class Edge { //간선 정보 관리하기 위한 클래스 int from; int to; int weight; public Edge(int from, int to, int weight){ //간선들 선언 this.from = from; this.to = to; this.weight = we.. [Algorithm 기초] 최단 경로 알고리즘 (다익스트라) 최단 경로 알고리즘 - 가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법 - 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는 데 사용 최단경로 알고리즘 종류 다익스트라, 벨만포드, 플로이드 워셜 다익스트라(Dijkstra) - 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘 - 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음 - 간선에 음의 가중치가 없어야 함 - 그리디 + DP 형태 알고리즘 복잡도 : O(ElogV) import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; //다익스트라 - 기본 사용방법 (매번 최소 간선을 구하기.. [Algorithm 기초] 다이나믹 프로그래밍 다이나믹 프로그래밍 (Dynamic Programming, DP) - 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식 - 중간 계산 결과를 기록하기 위한 메모리가 필요 - 한 번 계산한 부분을 다시 계산하지 않아 속도 빠름 분할 정복과의 차이 - 분할 정복은 부분 문제가 중복되지 않음 - DP는 부분 문제가 중복되어 재활용에 사용 그리디 알고리즘과의 차이 - 그리디 알고리즘은 순간의 최선을 구하는 방식(근사치) - DP는 모든 방법을 확인 후 최적해 구하는 방식 // 피보나치 수열 (일반 풀이 - O(n^2)) // 계산했던 부분도 다시 계산 public static int fib(int n) { if (n 이전 1 ··· 8 9 10 11 12 13 14 ··· 31 다음
