기타/자료구조9 우선순위 큐(Heap)과 트리맵(Red black Tree)의 차이 안녕하세요. 오늘 여러분들과 이야기해볼 주제는 바로 우선순위 큐와 트리맵(TreeMap)의 차이점에 대해서 이야기 해보려고 합니다. 이전 포스팅을 보신 분들이라면 아시겠지만 일단 우선순위 큐는 Heap 자료구조를 이용하고 트리맵은 Red-Black Tree를 이용합니다. 둘 다 트리 구조를 가지고 있기 때문에 어떤 상황에서 어떤 자료구조를 사용해야할지 한번 보도록 하겠습니다. 우선순위 큐 PriorityQueue는 Heap 자료구조를 기반으로 되어있습니다. 먼저 Heap 자료구조란 무엇인지를 확인해보겠습니다. Heap 자료구조는 최솟값, 최댓값을 빠르게 찾기위해 완전 이진 트리를 사용하는 자료구조입니다. 간단히 개념을 설명드리면 최소힙의 경우 root 노드가 값이 제일 작으며 트리는 부모 노드는 자식 노.. 2021. 2. 18. [자료구조] 코드로 알아보는 java의 PriorityQueue with Heap 안녕하세요. 오늘은 코드로 알아보는 java 시간압니다. 오늘 여러분들과 알아볼 Java의 자료구조는 PriorityQueue입니다. PriorityQueue는 우선순위 큐입니다. 우선순위 큐는 일반적인 FIFO 구조를 가지는 큐에 우선순위를 넣어 우선순위가 높은 노드부터 먼저가져올 수 있는 Queue입니다. Heap 자료구조 PriorityQueue는 Heap 자료구조를 기반으로 되어있습니다. 먼저 Heap 자료구조란 무엇인지를 확인해보겠습니다. Heap 자료구조는 최솟값, 최댓값을 빠르게 찾기위해 완전 이진 트리를 사용하는 자료구조입니다. 간단히 개념을 설명드리면 최소힙의 경우 root 노드가 값이 제일 작으며 트리는 부모 노드는 자식 노드보다 값이 작음을 항상 만족하는 트리입니다. 그리고 이렇게 H.. 2021. 2. 11. [자료구조] 코드로 알아보는 java의 TreeMap 안녕하세요. 오늘은 코드로 알아보는 java의 자료구조 시간입니다. 오늘 알아볼 자료구조는 TreeMap입니다. 바로 그러면 알아보도록 하겠습니다. TreeMap 기본적으로 TreeMap은 내부의 값들을 key 값을 기준으로 정렬하여 가지고 있습니다. 정렬된 순서를 알 수 없는 HashMap과는 차이가 있습니다. 아래 예제 코드를 한번 보도록 하겠습니다. @Test public void treeMapTest() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(7, "val"); map.put(8, "val"); map.put(9, "val"); map.put(10, "val"); map.put(11, "val"); map.put(12, "val");.. 2021. 1. 20. [자료구조] 코드로 알아보는 java의 EnumMap 안녕하세요. 오늘은 코르로 알아보는 java의 자료구조 시간으로 돌아왔습니다. 오늘 여러분들께 소개시켜드리고자 하는 자료구조는 EnumMap입니다. 이름에서 알 수 있듯이 Enum을 Key로 하는 자료구조인데요. HashMap을 평소에 사용하다 Sonar Lint의 정적분석에서 Enum을 Key로 사용한다면 EnumMap을 사용하는 것을 추천하기에 저도 EnumMap의 존재를 알게 되었습니다. 오늘은 제가 EnumMap 자료구조를 사용한 상황과 EnumMap은 HashMap과 어떻게 다른지 알아보는 시간을 가져보도록 하겠습니다. 문제의 상황 아래 소스는 제가 진행하고 있는 프로젝트의 코드 중 일부입니다. Game에 여러 Review를 남길 수 있도록 DB의 구조가 되어있습니다. 여기서 아래 메서드는 Re.. 2020. 12. 6. [자료구조] 코드로 알아보는 java의 LinkedHashMap 안녕하세요. 오늘은 오랜만에 다시 돌아왔습니다. 코드로 알아보는 java의 자료구조의 5번째 시간입니다. 오늘 알아볼 자료구조는 LinkedHashMap입니다. LinkedHashMap 이란 어떤 자료구조인지 HashMap과는 어떻게 다른지 알아보고 Java에서는 어떻게 구현되어 있는지 코드로 함께 확인하는 시간을 가지도록 하겠습니다. 해당 포스팅을 이해하기위해서는 먼저 HashMap에 대한 이해가 필요합니다. HashMap에 대해서 잘 모르시는 분들은 제가 이전에 포스팅한 HashMap의 자료구조를 한번 보시기바랍니다. HashMap을 순차적으로 읽으면 어떤 순서로 읽는가 ? HashMap은 Node를 꺼낼 때 넣은 순서를 보장하지 않는다고 합니다. 그렇다면 Node 순회에 대해서 읽는 순서는 어떻게 .. 2020. 10. 19. [자료구조] 코드로 알아보는 java의 HashSet 안녕하세요. Java의 자료구조를 알아보는 시간을 가지고 있습니다. 지금까지 List, Map에 대해서는 한종류씩 알아보았지만 아직 Set에 대해서는 알아본적이 없습니다. 그래서 오늘은 Set의 구현체 중 하나인 HashSet을 코드로 한번 알아보는 시간을 가지도록 하겠습니다. Set Set은 List와 다르게 중복을 허용하지 않는 자료구조입니다. 어떻게 중복을 허용하지 않을 수 있는지 코드와 함께 살펴보도록 하겠습니다. 상속과 멤버변수 public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable private transient HashMap map; // Dummy value to associate wit.. 2020. 2. 17. [자료구조] 코드로 알아보는 java의 LinkedList Java에서 List를 구현하는 구현체는 대표적으로 ArrayList, LinkedList, Vector가 있습니다. 저희는 저번 포스팅에서 ArrayList에 대해서 코드를 보며 내부 구조와 실질적인 시간복잡도를 파악해 보았습니다. 오늘은 LinkedList에 대해서 코드를 보며 ArrayList와는 어떻게 다른지 그 구조와 시간복잡도를 파악해보도록 하겠습니다. ArrayList와 LinkedList 우리가 일반적으로 알고 있는 ArrayList의 이미지는 위와 같습니다. String 형태의 "Hello Wo" char 배열에 저장한다고 하면 위와같은 형태가 될 것입니다. index를 가지고 있으며 index에 값을 저장하고 있는 형태입니다. 이런형태를 가짐으로써 RandomAccess가 가능하고 군집.. 2020. 2. 14. [자료구조] 코드로 알아보는 java의 ArrayList 안녕하세요. 오늘은 우리가 잘 사용하는 ArrayList에 대해 코드를 들여다 보고 내부는 어떻게 구성되어 있는지 확인해보도록 하겠습니다. 그리고 주요한 메서드 들은 어떤 로직으로 구현되어 있는지 알아보도록 하겠습니다. ArrayList ArrayList는 배열을 좀 더 편하게 쓸수있도록 Java에서 제공해주는 Class입니다. 일반 배열과는 다르게 메모리가 가능한한 추가할 수 있고 삭제에 대해서도 해당 index를 비워두기만 하는게 아니라 재정렬해주는 기능을 기본으로 제공해주고 있습니다. interface와 내부 변수 확인 public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Seriali.. 2020. 2. 12. [자료구조] 코드로 알아보는 java의 Hashmap HashMap이란 HashMap은 Key, Value를 저장하는 Map의 구현체 중 하나입니다. 자료구조에 Key를 넣으면 Value를 반환하도록 합니다. 그리고 HashMap은 Key를 Hashing을 하여 저장하여 빠르게 처리 그리하여 HashMap이란 입력과 삭제에 대해 시간복잡도가 O(1)인 자료구조라고 합니다. initialize 우리가 Java를 사용할때 HashMap을 사용한다고 한다면 가장먼저 초기화를 해야합니다. (Key, Value는 모두 String이라고 하겠습니다.) 그러면 아래와같이 초기화 할 것입니다. Map map = new HashMap(); 이때 내부에서는 어떤일이 일어나는지 보겠습니다. /** * Constructs an empty HashMap with the defau.. 2020. 1. 25. 이전 1 다음
