Java

Java 프림 알고리즘(Prim Algorithm)과 크루스칼 알고리즘(Kruskal Algorithm)에 대해

프림 알고리즘과 크루스칼 알고리즘은 MST(Minimum Spanning Tree)를 구하는 알고리즘이다. Spanning Tree 란 그래프 중 모든 정점이 간선으로 연결되어 있으면서 싸이클이 없는 그래프를 의미한다. Prim 알고리즘은 시작 정점에서부터 출발해서 신장트리 집합을 단계적으로 확장해나가는 방법이다. 동작 순서 1. 시작 단계에서는 시작 정점만이 MST 집합에 포함된다. 2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 3. n-1 개의 간선이 될 때까지 반복한다. Kruskal 알고리즘은 간선 선택을 기반으로 하는 알고리즘이다. 동작 순서 1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 2. 정렬된 간선 리스트에서..

자바에서 volatile 이란?

volatile 키워드를 변수앞에 쓴다는 것은 변수를 읽어들이거나 받아들일 때에 main memory에서 읽어들이고 main memory에 저장하겠다는 뜻을 갖는다. 다음과 같은 멀티 스레드 상황에서 CPU1이 Main Memory에 있는 value 값을 가져와서 +1씩 시키고 있을 때에 CPU2가 Main Memory에서 뒤늦게 value 값을 가져와서 사용할 때에 서로의 변수 값이 다르기에 오류가 발생할 수 있다. 이 때에 volatile 키워드를 사용해서 변수 앞에 붙여주면 위의 변수 값이 일치하지 않아서 생기는 오류를 해결할 수 있다. 하지만 언제나 적절한 것은 아니다. 흔한 멀티스레딩 문제의 오류가 날 수 있기 때문이다. 만약 CPU1이 Main Memory에서 부터 0의 값을 가진 count ..

위상정렬 자바로 구현하기, 백준2252_줄 세우기

위상 정렬은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. (위키 정의) 순서가 있는 노드를 차례대로 수행할 때에 쓰인다. 1 -> 3 2 -> 3 3 -> 4 다음과 같이 있는데, 2번을 수행하지 않았는데 4번이 먼저 나오게 된다면 오류라는 것이다. 순서에 맞지 않기 때문이다. 이러한 이유 때문에 위상 정렬을 사용하기 위한 전제는 싸이클이 없어야만 사용가능하다. 1->2->3->1 이러면 어느점이 시작점인지도 모르는 싸이클 그래프이다. 싸이클하지 않은 이 그래프를 DAG(Directed Acyclic Graph) 라고 부른다. (방향성 비순환 그래프) 구현 방식을 설명하고 바로 백준 문제로 예시를 들며 풀겠다. 1. 정점과 간선의 개수를 입력 받는다. 2. 결과를 받아줄..

Java Trie(트라이)란

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조이다. 제일 긴 문자열의 길이를 L, 문자열들의 수 M이라 두었을 때, 생성 시간복잡도 O(L*M) 탐색 시간복잡도 O(L) 이 걸린다. 아래는 구현 방법인데, 트라이는 코딩문제 기준으로 해당 문제의 조건에 따라 구현하는 것이 좋다. 무조건 밑을 따라가면 괜히 더 복잡해질 수도 있다. 그러니깐 아래의 구현코드를 보고 정말 제대로 이해를 한 다음에 트라이 기초문제들을 풀고 응용문제도 풀어보면서 감을 잡는게 정말 도움이 된다 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4..

Java HashMap 메서드 computeIfAbsent

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 static class made{ int x; made(int x) { this.x=x; } } public static void main(String[] args) { Map map = new HashMap(); System.out.println(map.computeIfAbsent('c',o->4)); System.out.println(map.get('c')); Map map2 = new HashMap(); made m =map2.get(1); if (m == null) { map2.put(1,new made(2)); } System.out.println(map2.computeIfAbsent(1,o->..

Java String 메서드 정리 (계속해서 추가)

123456789101112131415161718192021222324252627282930 int a=29; String binary=Integer.toBinaryString(a); //10진 > 2진 String oct=Integer.toOctalString(a); //10진 > 8진 String hex=Integer.toHexString(a); //10진 > 16진 String tmp="abcd"; String reverse_tmp=new StringBuffer(tmp).reverse().toString(); //문자열 뒤집기 String tmp2="12345"; tmp2=String.format("%"+6+"s",tmp2); //형식 바꾸기 앞에 공백 추가하거나 할 때에 유용 //tmp2=Stri..

Java 우선순위 큐, Priority Queue

컬렉션들 list, map, set ... 난 집어넣고 바로 최댓값이나 최솟값을 뽑아내는 그런 간편한게 필요한데..? 싶으면 우선순위 큐를 사용하면 된다. 힙을 이용하여 구현이 되어있다. 123456789101112131415161718192021222324252627282930313233343536 static class xy implements Comparable{ String x; int y=0; xy(String x, int y) { this.x = x; this.y = y; } @Override public int compareTo(xy o) { if(this.y>o.y) return 1; else return -1; } } public static void main(String[] args) ..

Java 형변환 정리

1234567891011121314151617181920212223242526272829303132333435363738394041 // Int to String int a=30; String b= Integer.toString(a); // String to Int String a="300"; Int b=Integer.parseInt(a); // Char to Int char a='3'; int b=Character.getNumericValue(a); int c=a-'0'; // Int to Char int a=3; char b= (char)(a+'0'); int a =10; char c='A'; System.out.println((char)('A'+a-10));cs