솧로그

Set Set은 ADT로 다음과 같은 특징을 갖는다. 중복을 허용하지 않는다. 저장 순서를 유지하지 않는다. HashSet 자바에서는 Set 자료구조의 구현체로 HashSet을 제공한다. HashSet은 다음과 같이 Set 인터페이스를 구현하고 내부적으로 HashMap을 사용한다. public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable { private transient HashMap map; private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap(); } } HashSet이 중복된 데이터를 허용하지..

Map Map은 ADT로 다음과 같은 특징을 갖는다. key-value 형태로 값을 저장한다. key는 중복을 허용하지 않고 value는 중복을 허용한다. 즉, 하나의 key에는 하나의 value만 가진다. 저장 순서를 유지하지 않는다. 해시 충돌 자바의 HashMap은 버킷의 위치를 정할 때 객체의 해시 값을 사용한다. 이때 해시 값은 int형으로 32비트이다. 따라서 어떤 데이터에 대해 나올 수 있는 해시 값은 2^32개이며 그 이상의 데이터들을 HashMap에 저장하려고 하면 몇 개의 데이터들은 해시 값이 같을 수밖에 없다. 그리고 2^32개의 해시 값에 따른 각각 다른 버킷을 메모리 공간에 할당한다면 이는 매우 비효율적이다. 따라서 HashMap에서는 메모리를 절약하기 위해 배열의 capacity..

우선순위 큐 우선순위 큐는 큐와 비슷하지만 먼저 들어온 데이터가 먼저 나가는 것이 아니라, 우선순위가 높은 데이터가 먼저 나간다. 큐: 먼저 들어온 데이터가 먼저 나간다. (FIFO) 우선순위 큐: 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐는 추상적인 개념이고, 주로 힙을 통해 구현된다. 힙 힙은 우선순위 큐의 구현 방식 중 하나로 주로 이진 트리 기반으로 구현된다. (이진 트리: 자녀가 최대 두 개인 트리) 최대 힙(Max Heap): 부모 노드의 키가 자식 노드의 키보다 크거나 같은 이진 트리이다. 최소 힙(Min Heap): 부모 노드의 키가 자식 노드의 키보다 작거나 같은 이진 트리이다. 힙의 주요 동작은 다음과 같다. insert: 힙에 데이터를 넣어주는데 이때 데이터의 키 값도 함께 ..

스택 스택은 가장 나중에 들어간 원소가 가장 먼저 나오는 구조이다. (LIFO) 사용 사례 스택 메모리 예를 들어 StackOverFlowError는 스택 메모리 공간을 다 썼을 때 발생하는 에러로, 주로 재귀 함수에서 탈출하지 못하면 발생한다. 자바에서의 스택 구현 자바는 Stack 클래스를 제공한다. Stack 클래스 외에도 LinkedList와 ArrayList를 통해 구현할 수 있다. 데이터 조회: Top에 있는 원소를 조회할 때는 O(1)의 시간 복잡도를 갖는다. 하지만 Top이 아닌 원소를 조회할 때는 해당 데이터를 찾을 때까지 수행해야 하므로 O(N)의 시간 복잡도를 갖는다. 데이터 삽입: LinkedList를 통한 구현에서는, 단순히 새로운 원소가 Top에 있는 원소를 가리키도록 참조를 변..

ArrayList와 LinkedList 둘 다 자바에서 제공하는 List 인터페이스의 구현체이다. ArrayList 내부적으로 배열을 사용하며 메모리 상에 연속적으로 위치한다. 배열(Array)과의 차이점은 다음과 같다. 자바를 기준으로, 기본 타입만 저장할 수 있는 Array와 달리 ArrayLists는 Object도 저장할 수 있다. ArrayList에 add를 통해 기본 타입의 데이터를 추가하면 오토 박싱이 사용된다. Array는 초기 사이즈가 고정되어 있고 변경이 불가하다. 반면 ArrayList는 이 또한 배열이기 때문에 초기 사이즈가 변경 불가한 것은 Array와 같지만, 사이즈가 가득 차면 내부적으로 새로운 메모리 공간을 할당받아(기존 용량의 1.5배) 새로운 배열로 데이터를 옮긴다. 배열의..