분류 전체보기

Java System.arraycopy() 에 대해

System.arrayCopy() 는 배열의 값을 원하는 크기를 원하는 위치에 복사할 때 쓰인다. 자매품으로는 clone() 메서드가 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class test { public static void main(String[] args){ int[] arr={1,2,3,4,5,6,7}; int[] arr2 = arr.clone(); int[] arr3 = new int[3]; System.arraycopy(arr, 4, arr3, 0, 3); for (Integer ar3 : arr3) { System.out.print(ar3); } } } Colored by Color Scripter cs 1~7 값을 가진 arr 배열이 있..

Java 다익스트라 알고리즘(Dijkstra Algorithm)에 대해

다익스트라 알고리즘은 그래프에서 출발점에서 목표점 까지의 최단거리를 구할 때 사용하는 알고리즘이다. 이 때의 그래프의 가중치는 양수여야만 한다. 음수인 경우에는 벨만 포드 알고리즘을 사용해야한다. 동작순서는 다음과 같다. 1. 방문하지 않은 정점 중에서 그 거리가 최소인 점 x을 선택한다. 2. x를 방문 처리한다. 3. x와 연결된 정점들을 검사한다. 4. x와 연결된 정점들까지의 거리가 x를 거쳐 그 점까지의 거리와 비교해서 더 크다면 후자를 전자에 삽입한다. 5. 1~4 반복 다음과 같이 진행된다. 구현코드는 다음과 같다. 동작원리를 외워두는 것이 좋다. 특정 문제에서는 간선의 방향성이 주어지기도 하고, 갈 수 없는 점이 나오기도 하기 때문이다. 1 2 3 4 5 6 7 8 9 10 11 12 13..

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