pinevienna blog

Hash는 key-value 쌍으로 데이터를 저장하는 구조! key 값에 해당하는 value를 즉시 찾기 때문에 O(1)의 시간복잡도를 가진다 key 값으로 value를 찾기 때문에 key 값은 중복을 허용하지 않으며, HashMap은 key의 null 값을 허용하고, HashTable은 허용하지 않는다 //직접 확인해보기 value 값은 중복값과 null 값을 가질 수 있다 HashMap은 멀티스레드에선 동시접근이 문제가 될 수 있기 때문에 HashTable을 사용해야 한다 (해시테이블의 함수엔 synchronized가 걸려있어 안전함) 하지만 synchronized 처리가 없는 해시맵이 속도가 훨씬 빠르므로 적절히 선택하기!! 위 그림은 collison, 충돌현상을 설명하기 위해 그렸음..ㅎㅎ 알고리..

Heap은 Complete Binary Tree를 기반으로 한 자료구조! 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됐다 힙에는 최소힙(Min Heap), 최대힙(Max Heap)이 있다 최소힙은 항상 작은 값이 상위레벨에 위치하도록 하고, 최대힙은 반대로 항상 큰 값이 상위레벨에 위치하도록 한다 최소힙에 데이터를 추가하면 마지막 레벨의 왼쪽부터 채워진다 그리고 힙 구조를 유지하기 위해서 자신의 부모노드와 값을 비교하게 된다 만약 부모노드의 값이 더 크다면 자리를 바꾸게 되는데, 이 과정을 부모노드의 값이 더 작을 때 까지 혹은 자신이 루트 노드가 될 때 까지 반복한다 한 번 돌때마다 절반씩 떨어지므로 O(log n)의 시간복잡도를 가진다 최소힙에서 최솟값을 찾는건 Root 노드 값을 가져..

Tree는 앞서 다뤘던 배열, LinkedList, Stack, Queue와 다르게 아래 그림과 같이 부모, 자식 관계를 가지며 계층이 있는 구조다 + 가장 말단, 자식노드가 없는 노드를 leaf(잎사귀)라고 함! 이진트리(Binary Tree)는 최대 두 개의 자식노드를 가지고 있는 트리를 말한다 세 개 이상의 노드를 가지면 더 이상 이진트리가 아님!! 이진 검색 트리(Binary Search Tree)는 이진트리에서 조건이 하나 더 붙는다 왼쪽 노드와 그 이하 노드들은 현재 노드보다 값이 작아야 하고, 오른쪽 노드와 그 이하 노드들은 현재 노드보다 값이 커야 한다 완전 이진트리(Complete Binary Tree)는 모든 노드들이 레벨별로 왼쪽부터 채워져 있는 트리를 말한다 더 정확히 말하자면, 마..

Queue도 stack과 마찬가지로 데이터를 저장하기 위한 자료구조 중 하나다 하지만 구조가 다르다 stack은 LIFO 구조였다면, queue는 선입선출, FIFO(First In First Out) 구조를 가진다 이렇게!!! 아 맞다 오른쪽이 Queue queue 역시 push, pop과 같은 역할을 하는 add/offer, remove/poll 이 있고 peek과 유사한 element와 peek 메서드도 있다 각각 exception을 발생시키냐 아니냐의 차이인데 전자쪽이 발생시키는 쪽이다 PriorityQueue는 우선순위 큐라고 하는데, 우선순위가 높은 것부터 꺼내는 특징이 있다 일반 queue는 LinkedList를 사용하는 것과 달리 pq는 배열에 데이터를 저장하며, '힙(heap)' 구조로 ..

역시 데이터를 저장하기 위한 자료구조 중 하나다 stack은 '쌓다'라는 의미를 가지고 있는데, 데이터를 쌓아 보관한다고 생각하면 편하다 예를 들어 책을 쌓아두면 가장 최근에 쌓아둔 것 부터 집어들 수 있다 (중간에서 빼낼 수 없다는 가정 하에) 마찬가지로 stack에 데이터를 저장하면 가장 마지막에 입력된 값부터 출력할 수 있어서 후입선출, LIFO(Last In First Out) 개념을 갖는다 자바에선 push, pop, peek, empty, search 메소드를 가진다 push, pop은 각각 입출력이고 peek은 맨 위에 저장된 객체를 꺼내지 않고 반환한다 empty는 비어있는지 알려주며 serch로 주어진 객체를 찾아서 그 위치를 반환한다 (배열과 다르게 1부터 시작, 못 찾으면 -1 반환)