Java

이번 포스팅에서는 JCF에서 LinkedList와 ArrayDeque가 어떻게 구현되어 있는지 살펴볼 것이다. 1.  ArrayDeque개념  Deque는 Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조를 의미한다. 그리고 이 Deque 인터페이스를 구현하는 클래스가 ArrayDeque이다. JCF에서 어떻게 구현되어 있나?  elements와 head, tailpublic class ArrayDeque extends AbstractCollection implements Deque, Cloneable, Serializable{ transient Object[] elements; // non-priv..

지난 포스팅에서 JCF를 다루었습니다. 이번 포스팅에서는 JCF의 ArrayList에 대해 살펴보겠습니다. ArrayList와 LinkedList 차이우선, ArrayList와 LinkedList의 개념적인 차이를 통해 ArrayList를 살펴보겠습니다. ArrayListArrayList는 데이터들이 쭉 늘어선 배열의 형식입니다.  ArrayList는 데이터의 인덱스를 가지고 있어서, 탐색(시간 복잡도: O(1))이 매우 용이하지만 데이터의 삽입과 삭제에서는 인덱스들의 위치를 조절해주어야 하기 때문에 O(n)의 시간 복잡도를 가집니다.  LinkedList 반면, LinkedList는 자료의 주소값으로 서로 연결되어있는 구조입니다. 내부적으로 양방향의 연결리스트로 구현되어있습니다. 탐색 시에 순차적으로 ..

이전 포스팅에서  Vector, Hashtable과 같이 포함되지 않는 클래스들이 있는데, 이것은 컬렉션 프레임 워크 이전에 만들어진 클래스들로 호환을 위해 남겨진 것을 언급했습니다.  이번 포스팅에서는 레거시 클래스인 Vector를 간단히 살펴보고 ArrayList와 비교한 것을 정리했습니다. 레거시 클래스: Vector Vector는 JDK 1.0부터 있었던 자료구조로 호환성을 위해 남겨진 클래스입니다.  Vector  vs ArrayList Vector 자체는 ArrayList와 기능이 거의 동일하지만, 한 가지 다른 것은 ArrayList는 비동기 방식이고 Vector는 동기 방식이라는 것에 있습니다. 실제 벡터의 메서드 내부를 들여다보면, synchroized가 선언되어있는 것을 볼 수 있습니다..

JCFJCF(Java Collections Framework)란 자바에서 데이터 구조를 구현하고 관리하기 위한 클래스와 인터페이스의 모음입니다. 쉽게 말해 자료 구조 종류의 형태를 자바 클래스로 구현한 모음집이라 볼 수 있습니다. 자바에서는 JCF를 통해 C언어와는 다르게 자료구조를 사용하기 위해서 직접 구현을 하는 것이 아니라, 인스턴스화를 해서 사용 가능합니다.  JCF는 크게 Collection 인터페이스와 Map 인터페이스로 나뉘게 됩니다. 기능적으로 공통된 부분이 많은 것끼리 모으다보니, 두 가지로 나뉘게 된 것입니다.  최상위의 Iterable 클래스는 하나의 데이터를 순회할 수 있는 특성이 있습니다. 하지만 Map 인터페이스는 두 개의 데이터를 한 쌍으로 다루는 특성이 있기 때문에 따로 분리..

문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 우선 순위 큐를 이용해 문제를 해결했습니다. 단순히 반복문 두 개로도 해결할 수는 있지만, 시간 복잡도가 300,000*300,000으로 제한 범위를 훨씬 넘어가게 됩니다. 풀이 방법은 다음과 같습니다. 1. 우선 보석을 무게에 대해 오름차순으로 정렬합니다. 그리고 무게가 같다면 가격에 대해 내림차순 정렬합니다. 2. 가방은 ..

문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 최소 공통 조상을 찾는 문제입니다. 위 문제는 sparse table이나 세그먼트 트리를 사용하지 않고, dfs로도 구현이 가능합니다. 우선 입력 값을 Arraylist[] 배열에 넣어 트리 상의 연결된 두 정점을 표현합니다. 그리고 parents[] 배열과 depth[] 배열을 통해 각 정점의 부모와 깊이를 저장합니다. (findDepthAndParents 메서드) 그럼 pare..