SYDev

이진 탐색 트리의 단점을 개선한 자료 구조 중 하나인 AVL 트리를 이해하고, 구현해보자. 이진 탐색 트리의 문제점 이진 탐색 트리는 다음 그림과 같이 균형이 맞지 않을수록 $O(n)$에 가까운 시간 복잡도를 보인다. 이렇듯 저장 순서에 따라 탐색의 성능에 큰 차이를 보이는 것이 이진 탐색 트리의 단점이다. AVL 트리의 이해 이진 탐색 트리가 자동으로 균형을 잡을 수 있도록 개선한 트리 중 하나가 AVL 트리이다. G. M. Adelson-Velskii와 E. M. Landis에 의해 고안되었으며, 그들의 이름을 따서 정해졌다. AVL 트리에서는 균형의 정도를 표현하기 위해 '균형 인수(Balance Factor)'라는 것을 사용한다. 리밸런싱(rebalancing): 균형을 잡기 위한 트리 구조의 재..

이진 탐색 트리에 대해 이해하고, 이를 구현해보자. 이진 탐색 트리 이진 탐색 트리(Binary Search Tree): '이진 트리'에 '데이터의 저장 규칙'을 더해놓은 탐색 알고리즘이다. - 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다. - 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. - 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다. - 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 이진 탐색 트리의 삽입과 탐색 구현 이전에 구현한 BinaryTree2.h와 BinaryTree2.c를 이용한다. 파일명: BinarySearchTree.h #ifndef __BINARY_SEARCH_TREE_H__ #define __BINARY_SEA..

데이터를 찾는 방법인 탐색에 대해 이해하고, 보간 탐색을 구현해보자. 탐색의 이해 탐색: '데이터를 찾는 방법'을 의미한다. 이전에 배운 '순차 탐색(linear search)'이나 '이진 탐색(binary search)'가 이에 해당한다. 효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민하기 전에, '효율적인 탐색을 위한 저장방법이 무엇일까'를 고민해야 한다. 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다. 보간 탐색 보간 탐색(Interpolation Search): 찾는 대상의 위치를 고려하지 않고 일관적으로 절반씩 줄여나가며 탐색을 진행하는 '이진 탐색'의 비효율성을 개선시킨 알고리즘이다. 보간 탐색의 구현 #include int Isearch(int ar[], int first, in..

복잡하지만 효율적인 정렬 알고리즘에 대해 알아보자. 힙 정렬 이해와 구현 힙 정렬(Heap Sort): 힙 자료구조를 이용하여 정렬을 진행하는 알고리즘이다. #include #include "UsefulHeap.h" int PriComp(int n1, int n2) { return n2-n1; //오름차순 } void HeapSort(int arr[], int n, PriorityComp pc) { Heap heap; int i; HeapInit(&heap, pc); for(i=0; i

퀵 정렬 공부하다가 문득 궁금해진 점, 중첩 while문에서 내부 while문을 돌리는 도중 바깥 while문의 중지 조건을 충족하면 그대로 멈출까 아니면 내부 while문이 모두 돌아가고 멈출까? 말로 하면 복잡하니 코드로 결과를 보자. #include int main(void) { int i=9; int j=0; while(i 바깥 while문의 중지 조건을 만족해도 안쪽 while문을 다 돌릴때까진 멈추지 않는다!!!

간단한 구조의 정렬 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬에 대해 이해하고 코드로 구현해보자. 버블 정렬 이해와 구현 버블 정렬(Bubble Sort): 인접한 두 개의 데이터를 비교해가며 정렬을 진행하는 알고리즘이다. #include void BubbleSort(int arr[], int n) { int i, j; int temp; for(i=0; i

자료구조 큐에 우선순위를 적용한 우선순위 큐를 이해하고, 힙을 이용해 우선순위 큐를 구현해보자. 우선순위 큐 우선순위 큐(Priority Queue): 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 규칙이 적용된 큐를 의미한다. 우선순위 큐의 구현 방법 배열 기반으로 구현하는 방법 연결 리스트를 기반으로 구현하는 방법 힙(heap)을 이용하는 방법 >> 배열과 연결리스트를 기반으로 하는 방법은 우선순위를 비교할 때, 모든 노드를 대상으로 비교를 진행하기 때문에, 노드의 수가 많아질수록 성능이 저하된다. 따라서, 일반적으로 우선순위 큐는 힙을 이용하여 구현한다. 힙 힙(heap): 완전 이진 트리의 일종으로, 우선순위 큐의 구현을 위해 만들어진 자료구조이다. 자식 노드와 부모 노드의 관계가 ..

계층적 관계(Hierarchical Relationship)를 표현하는 자료구조인 트리(Tree)를 이해하고, 트리를 대표하는 이진트리를 이용해 수식 트리를 구현해보자. 트리 트리(Tree): 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. 노드(node): 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소 간선(edge): 노드와 노드를 연결하는 연결선 루트 노드(root node): 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드(terminal node): 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드 내부 노드(internal node): 단말 노드를 제외한 모든 노드로 A, B와 같은 노드 레..