영운's 블로그

[자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision) [자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing) [자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점 [Java] 자바 Collection Framework의 HashMap은 어떤 해시 충돌 알고리즘을 사용할까? key, 해시 함수, 해시 값 등 해시의 기본 개념을 살펴보고 이를 바탕으로 해시 테이블(Hash Table) 자료구조를 알아본다. 또한 해시 테이블에서 필연적으로 발생하는 해시 충돌(Hash Collision)에 대해서도 살펴..

Heap이란? 힙은 '우선순위 큐'를 구현하거나 '힙 정렬'을 하기 위해 사용하는 자료구조이다. 힙은 이진 힙(Binary Heap)이라고 부르기도 한며 둘은 동일한 개념이다. '우선순위 큐'란 특정 우선순위 기준을 가지고 만든 큐를 의미한다. 사실 기존의 큐 또한 우선순위 큐에 속한다. 기존의 큐는 삽입된 순서 기준으로 먼저 삽입된 것에 우선순위를 부여한 우선순위 큐이라고 할 수 있다. 힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나눌 수 있다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙이다. 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙이다. 아래부터는 최대 힙을 가정하고 힙에 대해 서술하고자 한다. 힙의 규칙은 다른 트리 자료..

트리는 스택, 큐, 배열, 리스트와는 다르게 계층적 구조를 가져 굉장히 중요한 자료구조이다. 트리를 공부하며 느낀 것은 트리라는 개념도 어렵지만 트리를 설명하는데 나오는 여러 새로운 용어들이 발목을 많이 잡는 것 같다. 여기서는 트리 관련하여 나오는 주요 용어를 정리하고자 한다. 노드(Node) , 키(Key) 트리를 구성하는 하나의 요소를 노드라고 부르며 하나의 노드가 저장하는 값을 키라고 한다. 하나의 노드는 키와 자손을 가리키는 참조 변수(left, right)를 갖는다. 루트 노드(Root Node), 서브 트리(Subtree) 가장 낮은 높이에 존재하는 노드를 루트 노드(Root Node)라고 부른다. 트리의 접근은 언제라 루트 노드를 시작으로 접근할 수 있다. 해당 노드의 왼쪽 혹은 오른쪽에 ..

Queue(큐)는 Stack(스택)과 반대로 선입선출(First In First Out, FIFO)의 특징을 가지고 있다. 먼저 들어온 것이 먼저 나간다는 FIFO는 일상생활에서의 줄서기, 마트 재고관리부터 운영체제의 프로세스 관리, 너비 우선 탐색(BFS) 알고리즘까지 다양한 곳에서 이용되고 있다. 이번 글에서는 큐에 대해 간단히 알아보고 이를 직접 자바로 구현해 본다. Queue는 Stack과 마찬가지로 배열과 리스트 두 가지 방법으로 구현할 수 있다. 배열로 구현한 Queue 전체 구조 배열을 이용하여 큐를 만드는 경우 다음과 같은 원형 큐 형태로 구현해야 한다. 원형 큐 형태를 구현함으로서 배열의 첫 데이터의 index가 0이 아닐 수도 있게 된다. 이를 통해 배열의 마지막 index에 데이터가 ..