Hee's Story

숫자가 클 수록 우선순위가 높다는 문제에서 우선순위 큐를 내림차순으로 설정해서 사용하였다. 여기서 다음과 같은 이슈가 발생하였다. 우선순위 큐에 {3,7,6,2,4}를 넣었을 때 당연히 {7,6,4,3,2} 가 나올 줄 알았지만 {7,4,6,2,3}가 나왔다. 찾아보니 자바에서 우선순위 큐는 힙으로 구현되어있다는 것을 알았다. 이전에 정리했었는데..ㅎ 그래서 이번에는 제대로 이해하려고 한다. [자료구조] 힙(Heep) & 우선순위 큐 힙(Heep) 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료형으로 우선순위 큐를 위해 만들어졌다. 완전 이진 트리의 일종으로, 각 노드의 키값이 그 자식의 키 값보다 작지않거나(최대 힙), 크지 hee96-story.tistory.com 자바에서 우선순위 큐는 아래와 같이..

해시(Hash)/해시 함수(Hash Function)/해싱(Hashing)? 해시(Hash) 란 데이터를 다루는 기법 중 하나이며,해시 함수(Hash Function) 는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(Hash Value) 또는 해시코드 라고 하며, 키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing) 이라고 한다. 해시 테이블(Hash Table)? 해시 테이블(Hash Table) 은 키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조이다. 즉, 키(key)와 배열의 인덱스(index)를 이용하여 키를 저장하는 자료구조이다...

Stack 선형 자료구조의 일종으로 후입 선출(Last In First Out :LIFO) 방식이다. 즉, 나중에 들어간 원소가 먼저 나오는 특징을 가지고 있다. 데이터를 쌓아 올리는 구조로 먼저 Stack에 들어간 데이터는 맨 바닥에 깔린다. 따라서 늦게 들어간 원소는 맨 위에 놓이게 되고 호출시 가장 먼저 나가게된다. 입력(push), 출력(pop-java에서는 poll), 가장 위에 있는 데이터 확인(peek), 해당 값이 스택에서 몇번째 있는지(search) 등이 있다. 스택은 Random Access(비순차적 접근)이 불가능하다. 삽입/삭제는 O(1)의 시간 복잡도를 갖는다. 스택은 재귀 알고리즘을 사용할 때 유용하다. 재귀적으로 함수를 호출해야하는 경우, 임시 데이터를 스택에 넣고 재귀 함수를..

힙(Heep) 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료형으로 우선순위 큐를 위해 만들어졌다. 완전 이진 트리의 일종으로, 각 노드의 키값이 그 자식의 키 값보다 작지않거나(최대 힙), 크지 않은(최소 힙) 완전 이진 트리이다. 완전이진트리는 중복을 허용하지 않지만 힙은 허용한다. 우선순위 큐 우선순위가 있는 큐 가장 우선순위가 높은 데이터가 먼저 나간다. 배열, 연결리스트 힙 으로 구현이 가능하다. 힙으로 구현하는 것이 가장 효율적이다. 자료구조 삽입 삭제 정렬된 배열 / 순서 없는 배열 O(n) / O(1) O(1) / O(n) 정렬된 연결 리스트 / 순서 없는 연결리스트 O(n) / O(1) O(1) / O(n) 힙 O(logn) O(logn) 힙(Heap) 최대 힙(Max heap) 부모 노..

Chaining Hash Table /*Chaining HashTable*/ class ChainingHashTable { public static final int TABLE_SIZE = 10; private HashItems[] hashTable; //생성자 public ChainingHashTable() { this.hashTable = new HashItems[TABLE_SIZE]; } //hash code int getHashCode(String key) { int hashCode = 0; for (char c : key.toCharArray()) hashCode += c; return hashCode; } //hash code를 index private int convertToIndex(int..

LRU Cache는 자료구조는 아니지만 그래도 doubly linked list와 hash map을 사용해서 구현하였다는 것을 강조하기 위해 자료구조 카테고리에 넣었다. (나중에 변경할지도..) LRU Cache : Least Recently Used 캐시에서 메모리를 다루는 알고리즘 중 가장 많이 사용되는 알고리즘 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘 다음은 java를 사용한 예제 코드이다. import java.util.HashMap; import java.util.Map; public class LRUCache { private Map nodeMap; private int capacity; private node head; private node tail; private class..