suyeonme

B-트리(B-tree) 란? B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. -- 위키피디아 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관한다. 트리에 노드 삽입 및 삭제시, B트리의 규칙에 맞도록 재정렬하여, 왼쪽과 오른쪽 자식의 밸런스를 항상 유지한다. 따라서 O(logN)의 시간복잡도(탐색, 삽입, 삭제)를 가진다. 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다. Balanced Tree란? 일반적으로 트리 구조를 탐색하는 경우, O..

우선순위 큐(Priority Queue)란? 큐의 구조를 따르지만(FIFO, First In First Out) 우선 순위를 결정하고 높은 우선순위를 가진 요소를 먼저 꺼내서 처리하는 자료구조이다. 우선순위큐는 내부적으로 힙(Heap)으로 구성되어 이진트리의 구조로 이루어져있다. 따라서 O(N log N)의 시간복잡도를 가진다. Heap이란? Heap은 완전 이진트리로 구현되었으며 우선순위 큐를 위한 자료구조이다. 부모 노드의 값은 자식 노드의 값보다 크거나(Max Heap) 작아야(Min Heap)한다. 이러한 구조를 이용하여 최댓값과 최솟값을 빠르게 찾아낼 수 있다. 힙은 배열로 구현된다. 편의상 0번 인덱스는 사용하지 않는다. 왼쪽, 오른쪽 노드의 위치가 대소 관계를 반영하지 않는다. 즉 왼쪽 노..

그래프(Graph)란? 그래프는 정점(vertice)과 간선(edge)으로 이루어진 자료구조로, 트리(tree)도 그래프의 종류 중 하나이다. 하지만 그래프의 경우 정점마다 간선이 있거나 없을 수 있으며 루트 노드, 부모-자식이라는 개념이 존재하지 않는다. 그래프 사용 예시 포털 사이트의 검색 엔진, facebook의 네트워킹, 지하철 노선도등 그래프 관련 용어 용어 설명 정점(vertice) 노드(node)라고도 하며 데이터가 저장된다. 간선(edge) 링크(arcs)라고도 하며 노드간의 관계를 나타낸다. 인접 정점(adjacent vertex) 간선에 의해 연결된 정점이다. 단순 경로(simple-path) 경로 중 반복되는 정점이 없는것, 즉 동일한 간선을 자나가지 않는 경로이다. 차수(degree..

해시법(Hashing)이란? 데이터를 저장할 위치(index)를 간단한 연산으로 구하여 검색, 추가, 삭제를 효율적으로 수행한다. 해시 함수(Hash Function) 키값을 해시값(hash value)로 변환하는 과정을 해시 함수라고 한다. 충돌을 피하려면 해시 함수는 해시 테이블 크기 이하의 정수를 한쪽으로 치우치치 않도록 고르게 만들어야한다. 해시 테이블 크기는 소수(prime number)가 좋다고 알려져있다. 해시 테이블을 만드는데 사용되는 대표적인 해시 함수 목록이다. 키값이 정수(integer)인지에 따라서 해시 함수가 달라진다. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터로 해시를 생성하는 방법 Multiplication Method: 숫자로 ..

트리(Tree)란? 데이터 사이의 계층 관계를 나타내는 자료구조이다. 트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지로 연결되어있다. 그래프(Graph)의 여러 구조 중 무방향 그래프의 한 구조이다. 하나의 데이터 뒤에 여러개의 데이터가 존재할 수 있는 비선형 구조이다. (선형 구조: 데이터를 순차적으로 나열) 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클(cycle)이 없다. 트리를 사용한 대표적인 예시로, 파일 시스템(File System)이 있다. 파일 시스템에서 폴더는 루트 폴더에서 시작되어 가지를 뻗어나가는 모양을 한다. 트리 관련 용어 용어 설명 루트(root) 트리의 가장 윗부분에 위치하는 노드로, 하나의 트리에는 하나의 루트가 존재..

리스트(List)란? 데이터를 순서대로 나열한 자료구조이다. 선형 구조를 갖는 리스트에는 선형 리스트(linear list)와 연결 리스트(linked list)가 있다. 리스트에 있는 개별 요소를 노드(node)라고 한다. 노드의 구성 요소는 데이터와 다음 노드를 가리키는 포인터이다. 선형 리스트(Linear List) 데이터가 배열처럼 연속하는 메모리 공간에 저장되어 순서를 갖는다. 연결 리스트(Linked List) 데이터가 메모리 공간에 연속적으로 저장되어있지 않더라도 각각의 데이터안에 다음 데이터에 대한 정보를 갖고 있어 서로 연결(linked)된다. 연결 리스트의 구성 요소 머리 노드(head node): 리스트의 처음에 있는 노드 꼬리 노드(tail node): 리스트의 끝에 있는 노드 앞쪽..

1. Linear Queue(선형 큐)란? FIFO(First In First Out) en-queue: 큐에 데이터를 넣는 작업 -- O(1) de-queue: 큐에서 데이터를 꺼내는 작업 -- O(n) 데이터가 나오는 쪽은 front, 데이터를 넣는 쪽은 rear라고 한다. 1.1 선형 큐의 단점 큐에 데이터가 꽉 찼다면 데이터를 추가할 수 없다. de-queue시 요소를 하나씩 앞으로 옮겨야 하므로 복잡도가 O(n)이다. 2. Ring Buffer(Circular Queue)란? 원형큐는 배열의 맨 뒤가 맨 앞과 연결되었다고 보며 선형 큐의 문제점을 보완하기 위한 자료구조이다. 선형큐와 다르게 de-queue시, 배열 요소를 앞으로 옮기지 않아도 된다. enqueue시 rear 인덱스에 값을 저장하..

1. 스택(Stack)이란? LIFO(Last In First Out) push: 스택에 데이터를 넣는 작업 pop: 스택에서 데이터를 꺼내는 작업 푸시와 팝이 이루어지는 꼭대기는 top, 스택의 가장 아랫부분은 bottom이라고 한다. 2. 직접 스택 생성하기 static class IntStack { private int[] stack; // 스택 배열 private int capacity; // 스택 용량 private int stackPointer; // 스택에 쌓여있는 데이터 수 // 실행시 예외: 스택이 비어 있는 경우 public class EmptyIntStackException extends RuntimeException { public EmptyIntStackException() {};..