휴리스틱 탐색 해답을 구하기 위해 솔루션 공간을 탐색할 때 사용하는 기법 기존의 깊이우선탐색(DFS), 너비우선탐색(BFS) 등의 방법은 해답을 구하기까지 많은 시간 소요 경험에 따라 명백히 잘못된 방안을 제거해 탐색 공간을 좁혀가는 방법, 여기서 경험이 휴리스틱임 휴리스틱(heuristic)을 적용하여 탐색 속도를 향상 주어진 정보나 규칙을 이용해 불필요한 경로를 걸러내는 정보 탐색(information search) 방법… Continue Reading A star 알고리즘

그래프의 역사 수학자 오일러(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)

용어 우선순위 큐(Priority Queue) 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐의 구현 방법 배열을 기반으로 구현 연결 리스트를 기반으로 구현 힙(Heap)을 이용하여 구현 힙(Heap) 이진트리(Binary Tree) 중 완전이진트리(Complete Binary Tree) 최소힙(Min Heap) : 각 노드는 자식의 값보다 작아야 한다. 최대힙(Max Heap) : 각 노드는 자식의 값보다 커야… Continue Reading 09장 우선순위 큐(Priority Queue) – 힙(Heap) 이용

트리 관련 용어 노드(node) 간선(edge) 루트노드(root node) 단말노드(terminal node) 내부노드(internal node) 차수(degree) 레벨(level) 높이(height) = 깊이 를 사용하기도 함 차트 관련 문제 : 그림 출처(https://ko.wikipedia.org/wiki/트리_순회) 다음 트리를 보고 답하시오. 위 트리의 차수는? 위 트리를 Preorder 운행법으로 운행할 경우 다섯 번째로 탐색 되는 것은? 위 트기의 터미널 노드 수는? 위 트기의 내부… Continue Reading 08장 트리(Tree) – 이진트리(Binary Tree), 순회(Traverse)

연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #1 :S007_Deque.c 연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #2 연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #3 연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #4 연결리스트(LinkedList)를 이용한 덱(Deque) 구현 #5 연결리스트(LinkedList)를 이용한 덱(Deque) #6   연결리스트(LinkedList)를 이용한 덱(Deque) 완성 버전  

error: Content is protected !!