Study for Backend/Data Structure (21) 썸네일형 리스트형 [Data Structure 기초연습] HashTable - 해시 충돌 해결 - 개방 주소법 (이중 해싱) //해시 충돌 해결 - 개방 주소법 (이중 해싱) class MyHashTable4 extends MyHashTable{ int c; MyHashTable4(int size){ super(size); this.c = this.getHashC(size); } public int getHashC(int size){ int c = 0; if(size 2 ; i--) { boolean isPrime = true; for (int j = 2; j < i; j++) { if(i % j == 0){ isPrime = false; break; } } if (isPrime){ c = i; break; } } return c; } public int getHash2(int key){ int hash = 1 + key % .. [Data Structure 기초연습] HashTable - 해시 충돌 해결 - 개방 주소법 ( 제곱 탐사법 ) //해시 충돌 해결 - 개방 주소법 ( 제곱 탐사법 ) class MyHashTable3 extends MyHashTable{ MyHashTable3(int size){ super(size); } public void setValue(int key , int data){ int idx = this.getHash(key); if(this.elemCnt == this.table.length){ System.out.println("Hash table is full!"); return; }else if (this.table[idx] == null){ this.table[idx] = data; }else { int newIdx = idx; int cnt = 0; while (true){ newIdx = (newI.. [Data Structure 기초연습] HashTable - 해시 충돌 해결 - 개방 주소법 ( 선형 탐사법 ) import java.util.Hashtable; import java.util.Map; //해시 충돌 해결 - 개방 주소법 ( 선형 탐사법 ) class MyHashTable2 extends MyHashTable{ MyHashTable2(int size){ super(size); } public void setValue(int key , int data){ int idx = this.getHash(key); if (this.elemCnt == this.table.length){ System.out.println("Hash table is full!"); return; }else if (this.table[idx] == null){ //데이터가 할당되지 않은 상태라면 this.table[idx] = da.. [Data Structure 기초] HashTable HashTable(해쉬테이블) - key와 value를 대응시켜 저장하는 선형 데이터 구조 - key 를 통해 해당 데이터에 빠르게 접근 가능 - 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정을 Hashing이라고 함 - 병렬 프로그래밍을 지원하여 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황일 때 사용하기 적합 해시 충돌 해결 방법 1. 개방 주소법(Open Address) : 충돌 시, 테이블에서 비어있는 공간의 hash를 찾아 데이터를 저장하고 hash와 value가 1:1 관계 유지 비어있는 공간 탐색 방법에 따라 분류 - 선형 탐사법(Linear Probing) : 충돌 발생 지점부터 이후의 빈 공간을 순차적으로 탐사, 반복된 충돌 발생시 해당 지점 주변에 데이터가 .. [Data Structure 기초] Heap Heap (힙) - 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 - 반 정렬 상태이며 중복 값이 허용된다. Heap 시간복잡도 O(logn) import java.util.PriorityQueue; public class HeapExample { public static void main(String[] args) { // Integer를 저장하는 최소 힙 생성 PriorityQueue minHeap = new PriorityQueue(); // 요소 추가 minHeap.offer(5); minHeap.offer(2); minHeap.offer(8); minHeap.offer(1); // 최소값 확인 int minValue = minHeap.peek(); System.out.pr.. [Data Structure 기초] Deque Deque(덱 혹은 데크) - 양쪽에서 삽입과 삭제가 모두 가능한 자료구조 - 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. - 큐와 스택을 합친 형태로 생각할 수 있다. Stack 시간복잡도 삽입 : O(1) 삭제 : O(1) 탐색 : O(1) 연산 addFirst() 맨 앞에서 데이터를 삽입. 용량을 초과하는 경우 Exception 발생 offerFirst() 맨 앞에서 데이터를 삽입. 용량을 초과하는 경우 false 리턴 addLast() 맨 뒤에서 데이터를 삽입. 용량을 초과하는 경우 Exception 발생 offerLast() 맨 뒤에서 데이터를 삽입. 용량을 초과하는 경우 false 리턴 removeFirst() 맨 앞에서 데이터를 삭제. 비어있다면 Exception .. [Data Structure 기초] Linked List Linked List (연결 리스트) - 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조. - 데이터를 담고 있는 노드들이 연결되어있는데, 노드의 포인터가 이전이나 다음의 노드와의 연결을 담당하게 된다. - 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. - 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. - 실제 데이터를 저장시킬 때는 Node 타입의 배열에 저장된다. HashMap에 선언된 Node 타입 변수 및 클래스이다. Hashmap 시간복잡도 접근, 탐색 : O(n) 추가 , 삭제 : O(1) 연산 void addFirst(Object obj) 맨 앞에 객체(ob.. [Data Structure 기초] Hashmap Hashmap(해쉬맵) - Map 인터페이스를 상속받아 만들어진 클래스로 Map의 특성을 그대로 갖고있다. - Map은 Key & Value 한 쌍으로 구성된 Entry 객체를 저장하는 자료구조이다. - 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. - 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. - 실제 데이터를 저장시킬 때는 Node 타입의 배열에 저장된다. HashMap에 선언된 Node 타입 변수 및 클래스이다. Hashmap 시간복잡도 접근, 탐색 , 추가 , 삭제 : O(1) 연산 put(K key, V value) key와 value를 저장 remove(Object key) key와 일치하는 기존 데이.. [Data Structure 기초] Array Array(어레이) - 동일한 타임의 연관 데이터를 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 관리하기 위한 자료 구조, 선형 자료구조 - 처음 생성할 때 지정한 자료형만 넣을 수 있다 - 배열의 길이는 고정적이고 먼저 할당해줘야 한다. 따라서 메모리 사용에 효율적이다. Stack 시간복잡도 접근, 탐색 : O(1) 추가 1. 추가하려는 데이터가 맨 뒤가 아니라면, 추가되는 데이터 위치 이후에 있는 모든 데이터들을 한 칸씩 미뤄야 하므로 O(n)의 시간복잡도를 가진다. 2. 추가하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면, O(1)의 시간복잡도를 가진다. 삭제 1. 삭제하려는 데이터의 위치가 맨 뒤가 아니라면, O(n)의 시간복잡도를 가진다. 2. 삭제하려는 데이터의 위치가 맨 뒤이.. [Data Structure기초] Queue Queue(큐) - 줄을 지어 순서대로 처리되는 자료구조 - 먼저 들어온 데이터가 가장 먼저 나감 (First In First Out , 선입선출) - 마트의 재고관리 부터 운영체제의 프로세스 관리, 너비 우선 탐색(BFS) , 캐시 메모리, 버퍼 등에서 사용됨 Stack 시간복잡도 삽입( enqueue ) : O(1) 삭제( dequeue ) : O(1) 연산 enqueue(Object data) 데이터를 넣는 함수 ( add(data), offer(data) ) dequeue() 데이터를 꺼내는 함수( remove(), poll() ) peek() 요소를 읽어옴, 비어있으면 null isEmpty() 큐가 비어있는지 확인 isFull() 큐가 꽉 차있는지 확인 element() 큐가 비었을 때 요소를.. 이전 1 2 3 다음
