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..

객체지향 생활 체조 The ThoughtWorks Anthology 챕터중 객체지향생활체조부분 절차지향적인 코딩이 아닌 객체지향적인 코딩을 연습할 목적으로 만들어진 가이드 라인이라고 생각하면 된다. 때문에 매우 극단적이다. 책에서는 총 9가지 훈련법을 극단적으로 지켜서 1000줄짜리 코드를 짜는 연습을 하라고 되어있다. 그만큼 연습을 목적으로 이루어진 규칙이다. 때문에 처음에는 이해가 안되는 부분이 많았다. 굳이 이렇게 까지 해야하는 이유가 뭐지? 이런 규칙들은 차라리 객체지향방법에 어긋나는 것이 아닌가? 코드가 너무 낭비되는 것 아니가? 라는 생각이 들때도 많아서 읽으면서 물음표가 많았다. 쉽게 생각하면 드래곤볼의 손오공이 무거운 모래주머니 차고 움직이는 연습하는 것과 같다고 할 수 있다. 총9가지 규..

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

본페이지는 edwith 사이트의 "android developer" 부스트 코스의 5강.네트워크를 참고 하여 작성하였습니다. THREAD 하나의 Progress안에서 여러 일을 수행하려고 할때 Thread를 사용합니다. 예를 들어, 게임속 여러 몬스터들이 생성되는 것은 사용자가 움직이는 Thread와는 다른 Thread에서 진행되는 것입니다. 안드로이드에서 여러 Thread가 존재합니다. 네트워크로 데이터를 받아오는 경우는 많은 일들이 일어나기 때문에 별로의 Thread를 만들어 데이터를 받아와 화면에 보여주게 됩니다. 특히 안드로이드에서는 앱이 실행되면 메인 쓰레드가 실행이 되고 그안에서 다른 일들을 처리하는 개별 Thread들이 생성됩니다. 이때 여러 Thread들이 같은 리소스에 접근하게 될 수 있..

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..