SYDev

정점(vertex)과 간선(edge)로 표현되는 그래프 자료구조에 대해 이해하고, 구현해보자. 그래프의 이해 정점(vertex): 연결의 대상이 되는 개체 또는 위치를 의미한다. 간선(edge): 이들 사이를 연결하는 선을 의미한다. 다음과 같이 정점과 간선으로 구성된 자료구조를 그래프라고 한다. 그래프의 종류 무방향 그래프와 방향 그래프 무방향 그래프(undirected graph): 연결 관계에 있어서 방향성이 없는 그래프를 의미한다. 방향 그래프(directed graph) or 다이그래프(digraph): 간선에 방향정보가 포함되어 있는 그래프를 의미한다. 완전 그래프(complete graph): 각각의 정점에서 다른 모든 정점을 연결한 그래프를 의미한다. 방향 그래프의 간선의 수는 무방향 간선..

테이블의 핵심 주제라 할 수 있는 충돌 문제의 해결책을 몇 가지 알아보고, 구현해보자. 열린 어드레싱 방법 열린 어드레싱 방법(open addressing method): 충돌이 발생하면 다른 자리에 대신 저장하는 방법 선형 조사법, 이차 조사법, 이중 해쉬가 이에 속한다. 선형 조사법 선형 조사법(Linear Probing): 충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 방법이다. 옆자리가 비어있지 않을 경우, 옆으로 한 칸 더 이동을 해서 자리를 살핀다. 그러나, 이런 구조는 충돌의 횟수가 증가함에 따라 '클러스터(cluster) 현상(특정 영역에 데이터가 집중적으로 몰리는 현상)'이 발생하기 쉽다. 이런 선형 조사법의 단점을 극복할 수 있는 방법이 이차 ..

빠른 탐색의 성능을 보이는 테이블 자료구조와 테이블에 의미를 부여하는 해쉬 함수를 이해하고, 두 개념이 합쳐진 해쉬 테이블을 구현해보자. 테이블 자료구조의 이해 테이블(Table): 저장되는 데이터의 키(key)와 값(value)이 하나의 쌍을 이루는 자료 구조를 의미한다. 키(key)가 존재하지 않는 '값'은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다. 하나의 키(key)에 대응되는 값(value)는 하나이기 때문에, 테이블 자료구조의 탐색 연산은 $O(1)$의 시간 복잡도를 가진다. 배열을 기반으로 하는 테이블 #include typedef struct _empInfo { int empNum; int age; } EmpInfo; int main(void) { EmpInfo empInfoArr..

이진 탐색 트리의 단점을 개선한 자료 구조 중 하나인 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

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