huhsae's day huhsae's day

11657 타임머신 11657 타임머신https://www.acmicpc.net/problem/11657 Algorithm최단거리벨만 - 포드 알고리즘 CODEimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;​public class BOJ_11657 { static int N; static int M; static int[] dist; static int[][] map; static ArrayList[] list;​ static BufferedR..

1735 최단경로백준 1735 최단경로 알고리즘최단경로 ( 다익스트라) -개념정리 CODEimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;​public class BOJ_1753 {​ public static void main(String args[]) throws IOException { ArrayList[] graph; Queue pq = new PriorityQueue();​ //init​ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st ..

다익스트라 다익스트라자료구조그래프큐 특징최단거리를 구하는 알고리즘한지점에서 다른 정점까지의 각각의 최단거리를 구 할 수 있다. ( 모든 정점간의 최단거리 - 플로이드 )음의 가중치를 같는 간선이 나올경우 구할 수 없다(음이 나와도 구할 수 있는 경우 - 벨만포드) 관련 알고리즘최단 거리 알고리즘다익스트라플로이드벨만포드 개념그래프에서 시작정점을 정한다.시작 정점으로부터 다른 정점으로의 최단거리를 계속 업데이트 한다. dist[i]현재 지점까지의 최소 거리 dist[i]와 현재 정점 i와 연결된 정점 v의 가중치를 더한 값이 dist[v]보다 작을 경우 dist[v]를 업데이트 하고 우선순위 큐에 넣는다.우선순위 큐의 값이 없어 질때까지, 계속한다. dist[] 배열은 최대 값으로 초기화 한다.출발점 S의 ..

1238 파티https://www.acmicpc.net/problem/1238 TIPS최단경로 문제플로이드 다익스트라 알고리즘을 해결할 수 있다.플로이드로 풀경우 O(|V|^3^) 속도 때문에 안풀리 수 있다고 하는데, 조건과 관계없이 풀수 있다.플로이드로 풀경우 단순히 학생집에서 파티장의 최단거리, 파티장에서 학생집까지의 최단거리를 더해서 값을 구할 수 있다.다익스트라로 풀경우, 파티장에서 학생집까지는 쉽게 구할수 있다. 하지막 역은 모든 정점을 다시 구해야 하는 불편함이 있다. 이를 해결하기 위해서, 간선의 방향을 바꿔서 파티장에서 각 노드까지의 간선의 합을 구하면 쉽게 구할 수 있다고 한다. CODEimport java.io.BufferedReader;import java.io.IOException..

MTSMTS, 최소신장트리, 최소스패닝트리 최소신장트리는 이름에서 알 수 있듯이 트리와 관련되어있다. 정확히 따지자면 그래프에서 특정 트리를 찾아내는 것이다. 주어진 그래프에서 모든 노드를 포함하는 가중치가 최소(또는 최대)가 되는 트리를 찾는 것이다. 왜 신장이라는 단어가 들어가는 지는 잘 모르겠지만, 모든 노드를 포함하는 중복되는 간선이 없음을 뜻하는 것일 듯 하다. 즉 간선의 수는 무조건 노드의 수보다 하나 작아야 한다는 것이다. 또 다른 조건은 앞에서 설명했던 내용에서 유추할 수 있듯이 사이클이 발생해서는 안된다는 것이다. 트리, 그래프에서 대해서 모른다면 다른 곳에서 찾아보고 오자. Kruskal & Prim 최소신장트리를 구하는 알고리즘은 Prim과 Kruskal알고리즘이 있다. 포인트는 Kr..

https://www.acmicpc.net/problem/1826 https://github.com/huhsay/algorithm/blob/master/heap/src/BOJ_1826.java TIPS 우선순위큐(힙) ALGORITHM 두개의 우선순위 큐를 사용합니다.먼저 입력값을 받으며, 거리를 기준으로 가까운 주유소를 정렬합니다. (stations) while문으로 내가 갈 수 있는 거리가 목표지점에 미치지 못한다면 목표지점을 찾을 때까지 반복하도록 합니다.while문 안에서 현재 내가 도달할수 있는 범위에 있는 주유소가 있다면stations 배열에서 객체를 꺼내어 새로운 우선순위 큐에 넣습니다.(reachableStations)reachableStation은 연료가 많은 순으로 정렬됩니다. 만약 r..