반응형 Algorithm66 다익스트라(dijkstra) *목차 1. 다익스트라 알고리즘이란? 2. 시간복잡도 3. 수도코드 4. 백준예제 5. 생각할 점 1. 다익스트라 알고리즘이란? 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 방향그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다. 2. 시간복잡도 (V는 정점, E는 정점의 이웃노드) 처음 고안한 알고리즘은 O(V^2)의 시간복잡도를 가졌다. 이후 O((V+E)logV)의 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나왔다. O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(.. 2020. 7. 13. PriorityQueue / Deque *PriorityQueue Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. null은 저장할 수 없고 NullPointerException이 발생한다. 저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다. (힙은 이진트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다.) import java.util.*; public class PriorityQueueExam { public static void main(String[] args) { // TODO Auto-generated method stub Queue pq = new PriorityQueue(); // Adding it.. 2020. 7. 10. Set<E> vs Map<K,V> Set은 중복을 허용하지 않고 Null값은 1개를 허용하고 순서를 보장하지 않는다. Map은 key 중복은 허용하지 않고 value중복은 허용하며 Null값은 key값의 경우 1개, value의 경우 여러개를 허용하고 마찬가지로 순서를 보장하지 않는다. *Set 타입 메소드 설명 boolean add(E e) 데이터를 set에 추가한다. boolean contains(Object o) 데이터가 있는지 확인한다. boolean remove(Object o) 데이터를 제거한다. ex) HashSet, LinkedHashSet, TreeSet, SortedSet import java.io.*; import java.util.*; import java.util.Map.Entry; public class Main.. 2020. 7. 10. 백준 11720 / 숫자의 합 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(br.readLine()); String line = br.readLine(); int res=0; for(int i=0;i 2020. 7. 9. 백준 10989 / 수 정렬하기 3 1. int[] 배열 이용 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(br.readLine()); int[] list = new int[10000]; StringBuilder sb = new StringBuilder(); for(int i=0;i 2020. 7. 9. 백준 11652 / 카드 int 32bit ( 4byte ) -2^31 ~ 2^31 -1 long 64bit ( 8byte ) -2^63 ~ 2^63-1 카드에 적혀 있는 수가 -2^62보다 크고 2^62보다 같거나 작다고 했으므로 long의 범위를 사용할 것!!! 1. Map을 이용하기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parse.. 2020. 7. 9. 백준 10814 / 나이순 정렬 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(br.readLine()); String line=""; List list = new ArrayList(); String[][] array = new String[num][2]; for(int i=0;i 2020. 7. 9. 백준 11650 / 좌표 정렬하기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(br.readLine()); List list = new ArrayList(); for(int i=0;i 2020. 7. 9. StringTokenizer vs Split StringTokenizer String StringTokenizer(String str) white space, new line, tab 등을 기준으로 token을 나눈다. String StringTokenizer(String str, String delim) delim을 기준으로 token을 나눈다. String StringTokenizer(String str, String delim, boolean flag) flag가 true이면 delim도 token으로 포함해서 나눈다. flag가 false이면 delim은 token으로 포함하지 않는다. (default) boolean hasMoreTokens() token이 더 있는지 확인 boolean nextToken() 다음 token 반환 Objec.. 2020. 7. 7. 이전 1 ··· 4 5 6 7 8 다음 반응형
