본문 바로가기

프로그래밍 언어 (プログラミング言語)

JAVA의 정렬 1. 기본형 배열의 정렬 오름차순 정렬 Arrays.sort() int[] arr = {1, 26, 17, 25, 99, 44, 303}; Arrays.sort(arr); System.out.println("Sorted arr[] : " + Arrays.toString(arr)); Output: Sorted arr[] : [1, 17, 25, 26, 44, 99, 303] 내림차순 정렬 내림차순으로 정렬하려면 sort()의 인자에 추가로 Collections.reverseOrder()를 전달해야 합니다. Integer[] arr = {1, 26, 17, 25, 99, 44, 303}; Arrays.sort(arr, Collections.reverseOrder()); System.out.println("S.. 더보기
Equal(), HashCode() in JAVA eqaul 메서드와 hashCode 메서드를 이해하기 위해서는 JAVA에서 HashMap, HashSet, HashTable이 어떤 원리로 동작을 하는지와 같이 설명을 하면 이해가 쉽다. 일단 equal 메서드와 hashCode 메서드 모두 Object 클래스에 있다. equal 메서드는 보통, 객체를 생성하는 순간 자동으로 오버라이딩이 되어서 두 객체의 레퍼런스값을 비교하는 것이 아닌, 두 객체 내부의 필드값들이 같은지 다른지를 비교한다. ( 객체의 레퍼런스값은 == 연산자로 비교 ) hashCode는 JAVA에서 객체를 Unique하게 식별하기 위한 정수값이며, hashCode()에서 hash function을 사용하 여 생성을 한다. JAVA의 HashTable의 동작 원리( HashMap, Has.. 더보기
JAVA에서의 동기화 기법(모니터 etc) JAVA에서 모든 객체는 내부적으로 모니터를 가진다. 1. 모니터의 mutual exclusion 기능은 synchrnozied 키워드로 사용한다. 2. JAVA의 모니터는 condirtion variable을 하나만 가진다. ( 두 개 이상의 cv를 원한다면 따로 구현이 필요) 3. JAVA 모니터의 세 가지 동작(Operation) a) wait b) notify(=signal) c) notifyAll(=broadcast) bounded producer/consumer problem WITH JAVA java.util.concurrent에는 동기화 기능이 탑재된 여러 클래스들이 있으니 참고하자. 더보기
StringBuilder의 사용 이유와 System.out.print()의 실행 속도 백준 1655문제를 JAVA로 풀다가 계속해서 시간초과가 떠서 심히 빡이 쳤다. 내가 짠 C++ 코드를 그대로 JAVA로 Porting을 했음에도 시간초과가 떴다. 결국 원인은 System.out.print(max_heap.peek())에 있었다. 소스 코드(시간초과) BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PriorityQueue max_heap = new PriorityQueue(Collections.reverseOrder()); PriorityQueue min_heap = new PriorityQueue(); int n = Integer.parseInt(br.readLine());; for( int x = .. 더보기
자바에서의 Priority_Queue 우선 C++에서의 Priority Queue는 default가 최대힙으로 구현이 된다. 알고리즘 문제를 자바로 풀면서, 당연히 자바도 default가 최대힙인 줄 알았으나 , 자바에서는 defualt가 최소힙이였다. ( 일반적으로, Heap이라고 함은 최대Heap을 말한다.) C++ priority_queue max_heap; // less는 default이므로 생략이 가능. priority_queue min_heap; // 최소힙 구현 시, greater를 넣어 줌 . JAVA PriorityQueue max_heap = new PriorityQueue(Collections.reverseOrder()); PriorityQueue min_heap = new PriorityQueue(); JAVA의 Pri.. 더보기
STL lower_bound() upper_bound() 이번에는 모든 분들이 다 아시는 sort를 제외한 다른 sorting 함수와 lower(OR upper)_bound()를 알아보도록 하겠습니다. [binary_search(arr_begin,arr_end,find_value) : 검색해주는 함수로서 찾는 값이 존재하면 True, 아니면 False를 리턴한다.] 이진 탐색(binary search)를 사용하는데, 정렬이 되어 있다는 가정하에 값을 빨리 찾고 싶을 때 사용합니다. arr_begin - 시작 arr_end - 끝 find_value - 찾고자 하는 값 [1 4 5 7 8 11 12 12 16 21 35] 11개의 값이 있다고 가정하자, 만약 여기서 21이라는 값을 찾고 싶다면, 어떻게 할까? 반복문을 사용해서 처음부터 끝까지 비교를 해 보면 됩.. 더보기
STL Binary Search function binary_search(target)는 target value이 들어 있는 배열(or vector)의 인덱스를 반환하는 줄 알았으나, bool 값을 반환을 한다. STL에서 지원하는 binary_search()는 세 개의 매개변수를 받는다. 첫 번째는 찾고자 하는 범위의 시작점, 두 번째는 찾고자 하는 범위의 끝점이다. 이 둘은 반복자(iterator)로 주어져야 한다. 세 번째 매개 변수는 찾고자 하는 수이다. 찾고자 하는 수를 매개 변수로 전달하면 된다. // binary_search(반복자.시작점, 반복자.끝점, 찾고자 하는 값); // 은 찾고자 하는 값을 찾으면 true를, 찾지 못하면 false를 반환한다. vector nums; int target = 3; bool isFound = bin.. 더보기
(ordered) Map vs Unordered Map C++에서 map은 red-black tree로 구현이 된다. Unordered Map은 hash table로 구현이 된다. 차이점 1. map과 unordered map의 큰 차이점은 구현에서부터 이미 차이가 난다. 2. map은 탐색 연산의 시간 복잡도가 O(log N)인 반면 unordered map은 hash table을 이용하므로 O(1) 3. map은 AVL 트리와 같이 삽입/삭제 시 항상 밸런스를 맞추기 위해 정렬을 하지만, unordered map은 그렇지 않다. 결론 1. 정렬을 필요로 하는 경우가 아니라면 연산 속도 면에서 unordered map이 훨~~~~~씬 유리 2. 일반적으로 key값이 짧고, int형인 경우 unordered map을 권장( 그 이유는 hash function.. 더보기

티스토리툴바