B-Tree의 개요 B-Tree의 개념 - 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조 - 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 자료구조의 일종 - 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되지만 B-트리는 상향식으로 구성됨. - B는 Balanced의 의미이며, leaf node가 한쪽 방향으로 쏠리는 현상이 적음 - B-Tree 에서 B를 Bi로 인식하는 사람들이 많으나, Balanced이다. 일반적인 트리와 다르게 자식노드가 3개 이상이 될 수 있기 때문이다. B-Tree의 특징 각 노드는 1/2이상 채워져야 하며 모든 리프 노드(leaf node)는 같은 레벨 (균형 트리) 탐색, 추가, ..
퀵 정렬(Quick Sort)의 개요 개념 기준 값인 피벗(Pivot)을 중심으로 작은 값은 좌측에 큰 값은 우측에 위치시켜 분할과 정복(Divide and Conquer)으로 정렬을 수행하는 알고리즘 특징 빠른 속도 : 선택정렬과 삽입정렬보다 빠른 정렬 수행 (다만 힙정렬보다는 느림) 분할과 정복 : 기준 값(Pivot)을 기준으로 앞, 뒤의 비교를 통해 스왑(Swap) 수행 재귀적 수행 : 분할을 마친 후 분할된 부분에서 반복 수행 - 수행시간 복잡도 : O(n-log2n) 퀵 정렬의 과정 1. 리스트(5,3,8,4,6,3,2)에서 피벗으로 4의 값을 선택 2. 4보다 작은 값(3,3,2)은 좌측, 4보다 높은 값은 (5,8,6) 3. 좌측과 우측에서 다시 Pivot(좌측은 3, 우측은 8)을 선정하..
버블 정렬(혹은 거품 정렬)이란 - 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬하는 방식 - 두개의 인접한 원소를 검사하여 정렬을 하는 방식으로 시간 복잡도가 O(n$^2$)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용하는 방식이다. 버블정렬 코드, Java 예제 1 class BubbleSort { void bubbleSort(int array[]) { int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) { // swapped keeps track of..
컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택(Stack)과는 반대되는 개념이다. 일반적으로 순차적으로 실행이 되어야 하는 프린터의 출력이라든지, 메세지 처리기, 프로세스 관리등에서 활용이 된다. 이렇게 줄을 서는 개념이 Queue이다. 1. First In First Out의 자료구조, 큐의 개념- 먼저 들어간 데이터가 먼저 나오는 선입선출 FIFO 자료구조형 2. 큐의 구성도 및 자료구조와 연산가. 큐의 구성도 나. 큐의 자료구조와 연산 createQueue() : 큐 생성/ 최대 n 개의 원소를 가질 수 있는 큐 생성deleteQueue() : 큐..
아래 그림 하나로 모든 것을 설명할 수 있는 것이 Stack 이다. 스택은, 선형구조(LIFO) 즉, Last In First Out 기반의 자료구조이고,Push라는 것으로 자료를 저장하고, Pop이라는 연산으로 가장 최근에 저장된 자료를 사용, 삭제하게 된다. 좀 더 쉽게 설명하자면, 접시를 들 수 있는데...접시를 계속 쌓이두면, 사용할 때도 가장 최근에 쌓아둔 접시를 사용하게 된다.... 그럼, 이 불공평(unfair)한 자료구조는 언제 사용하는 것일까?? 대표적인 사용출처는 "인터럽트 처리", "루틴의 복귀", "함수 호출할 때 인수 전달"를 할 때 쓸 수 있다.어떠한 작업을 할 때 현재의 상황에 우선순위의 작업을 등록하여, 처리하고 복귀할 때 스택만큼 좋은 자료구조는 없기 때문이다. 스택에서 사..
