無테고리 인생살이

힙이란? : 완전 이진 트리 형태이며, 우선순위 큐를 위해서 만들어진 자료구조 완전 이진 트리(complete binary tree) : 이진 트리 종류 중 하나로, 마지막 level을 제외하고 모든 level이 두 자식 노드로 완전히 채워져 있는 이진 트리 (level - 이진 탐색 트리 게시글의 그림 확인) 언제 사용하는가 : 우선순위 큐와 같이 최대/최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 사용된다. EX) java.util.PriorityQueue 사용 이유 : 배열을 통해 최대/최소값 찾으려면 O(N)이 걸리지만, 힙은 O(log N)이 걸린다. (시간복잡도를 줄이기 위해서) 힙의 종류 1. 최대 힙 : 부모노드의 값이 자식노드 값보다 크거나 같다 (Root node가 최대값) 2..

트리 : node, branch를 사용한 자료구조 이진트리 : branch가 최대 2개인 트리(=최대 2개의 자식노드를 갖는 트리) 배열과 연결리스트로 구현할 수 있지만, 일반적으로 연결리스트로 이진트리를 구현한다. (노드 - 1.데이터 2.왼쪽 자식 포인터 3.오른쪽 자식 포인터) 이진 탐색 트리 (BST) : 부모노드보다 작은 값은 왼쪽 자식노드, 큰 값은 오른쪽 자식노드에 위치시키는 특성을 가진 이진트리. 같은 값을 같는 노드가 없다는 특징이 있다. 이진 탐색 트리의 용도 : 데이터 탐색 시간복잡도 : O(log N) 장단점 장점 : 탐색속도 O(log N)으로 개선 단점 : 균형이 무너진 최악의 경우, O(N)까지 시간복잡도가 증가할 수 있다. EX) 4라는 데이터를 탐색할 때, O(N)의 시간복..

Load Factor란? 용량 대비 데이터가 어느정도 찼을 때 내부적으로 사이즈 확장을 필요로하는 자료구조에서 사용되는 개념이다. 언제 사이즈를 늘려야하는지, 즉, 몇 번째 데이터를 추가할 때, 사이즈를 늘려야 하는지를 결정하는 척도, 기준 default 로드팩터는 0.75f 이다. Load Factor를 어떤 용도로 사용할까? 사이즈가 가변적인 자료구조에 쓰이며 current capacity와 곱을 이뤄, 사이즈를 증가시켜야 하는 시기(=임계점)을 결정하는데 사용된다. 로드팩터가 존재하는 대표적인 자바 컬렉션 프레임워크 ArrayList HashMap Hashtable ConcurrentHashMap HashSet 등등.. 일반적으로 default load factor는 0.75이지만, ArrayLis..

얕은 복사(Shallow copy) : 다른 객체에 원본 객체의 주소값을 복사해 할당하는 것 public static void main(String[] args) { ArrayList list = new ArrayList(); // initialCapacity : 10 list.add("original obj"); ArrayList list2 = list; // Shallow copy list2.add("copy obj"); // 원본 객체 출력 System.out.println(list.toString()); // [original obj, copy obj] // 사본 객체 출력 System.out.println(list2.toString()); // [original obj, copy obj] } 같..

ArrayList의 사이즈 확장을 코드로 먼저 확인하기 add Method의 flow 따라가며 이해하기 ArrayList의 사이즈가 언제 얼만큼 확장되는지 코드를 통해 먼저 확인해보자. ArrayList 객체를 생성하고 20개의 데이터를 순차적으로 담으면서, 언제, 얼만큼 capacity를 늘리는지 단순히 확인하기 위한 코드입니다. 가독성을 위해 static 메서드를 사용했고 main 메서드만 확인하시면 됩니다 ! 이 글을 참고해서 ArrayList의 capacity를 구하는 메서드를 작성했습니다. How to get the capacity of the ArrayList in Java? Its known that Java ArrayList is implemented using arrays and init..