그래프의 역사 수학자 오일러(Euler)에 의해 고안 1736년 쾨니히스베르크 다린 문제 모든 다리를 한 번씩만 건너서 처음 출발한 장소로 돌아올 수 있을까? 정점 별로 연결된 간선의 수가 모두 짝수이어야 간선을 한 번씩만 지나서 처음 출발했던 정점으로 돌아올 수 있다. 그래프 용어 정점(vertex) 간선(edge) 무방향 그래프(undirected graph) 방향 그래프(directed graph, digraph) 완전… Continue Reading 14장 그래프(Graph)

테이블 : 원하는 바를 단번에 찾아내는 방식 키(Key)와 값(Value)의 한 쌍으로 저장되는 구조 시간복잡도 : O(1) 테이블 소스 : S013_Table.c 테이블의 문제점 사원번호가 : 201900000 ~ 201900099으로 100명이 근무하는 회사에 대해 프로그래밍 한다면 위 코드를 어떻게 수정해야 하는가? 해쉬(Hash) 코드 사용 샘플 소스 : S013_TableHash.c 해쉬(Hash) 방법 자릿수 선택(Digit Selection)… Continue Reading 13장 테이블(Table)과 해쉬(Hash)

AVL 트리 : G. M. Adelson-Velskii와 E. M. Landis에 의해 1960년대 고안됨 균형 인수 = 왼쪽 서브 트리의 높이 – 오른쪽 서브 트리의 높이 리밸런싱(rebalancing) : 균형을 잡기 위한 트리 구조의 재조정 LL 회전 : LL(Left-Left) 상태인 트리를 균형을 잡기 위한 회전 RR 회전 : RR(Right-Right) 상태인 트리를 균형을 잡기… Continue Reading 12장 탐색(Search) 2 – AVL 트리(AVL Tree), 균형트리

순차 탐색(Linear Search) 이진 탐색(Binary Search) 이진 탐색의 변형으로 보간 탐색을 들 수 있음 보간 탐색(Interpolation Search) : S011_InterpolSearch.c 이진 탐색 트리(Binary Search Tree)  특징 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한… Continue Reading 11장 탐색(Search) 1 – 이진탐색트리(Binary Search Tree)

단순 정렬 알고리즘 버블 정렬(Bubble Sort) : O(n2) 선택 정렬(Selection Sort) : O(n2) 삽입 정렬(Insertion Sort) : O(n2) 복잡하지만 효율적인 정렬 알고리즘 힙 정렬(Heap Sort) : O(nlog2n) 병합 정렬(Merge Sort) : O(nlog2n) 퀵 정렬(Quick Sort) : O(nlog2n) 기수 정렬(Radix Sort) : O(ln) -> O(n) 예상문제 : {13, 212, 14, 7141, 10987,… Continue Reading 10장 정렬(Sorting)

error: Content is protected !!