I. 힙 정렬 (Heap Sort)의 개요가. 힙 정렬의 정의트리 중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진 트리인 힙(Heap)을 만들기 위한 정렬 방법나. 힙 정렬의 특징힙 구조에서 가장 큰 값의 위치는 루트에 있음.배열에 저장하는 것이 효율적임.수행시간 복잡도: O(n·log2n) Ⅱ. 힙 정렬의 삽입∙삭제 과정 및 사례가. 힙 정렬의 삽입과정 및 사례새로운 노드의 위치를 정한다.삽입할 데이터를 새로운 노드에 놓는다.새로운 노드와 부모를 비교하여 부모가 더 작으면 바꾸는 과정을 루트에 도달할 때까지 계속한다.⇒⇒⇒void insert_max_heap(element item, int *n) {int i;if(HEAP_FULL(*n)) {fprintf(stderr,”The h..

I. 백트래킹(Back Tracking) 알고리즘의 개요가. 백트래킹 알고리즘의 정의깊이우선탐색(DFS)기법에 Pruning 기법을 적용하여 Promising 검토와 Back Tracking 을 활용하여 탐색 성능을 개선한 알고리즘 나. 백트래킹의 특징특징설명깊이우선탐색 기법탐색 트리의 최초의 하위노드 (child node) 를 확장하여 목표상태 (goal state) 가 발견될 때까지 더 깊이 (deeper and deeper) 확장하는 무정보 탐색(Uninformed or Blind Search) 방법Pruning 기법유망하지 않은 노드를 포함한 경로를 더 이상 고려하지 않도록 가지치기 표시를 하는 기법 Ⅱ. 백트래킹의 순서도 절차가. 백트래킹의 순서도나. 백트래킹의 절차절 차핵심 개념설명1. 깊이우..

I. 최단 경로 탐색의 개요가. 최단 경로 탐색의 정의그래프 내의 한 vertex에서 다른 vertex로 이동할 때 가중치의 합이 최솟값이 되는 경로를 탐색하는 알고리즘 Ⅱ. 최단 경로 탐색 알고리즘가. 다익스트라 알고리즘 (Dijkstra Algorithm)* 사이클이 없는 방향성에만 적용* 가중치 합 최소* Link State 알고리즘 활용각 vertex들은 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비모든 vertex들은 경로의 길이를 무한대로 초기화시작 vertex의 경로의 길이를 0으로 초기화하고 최단 경로에 추가연결된 vertex들의 경로 길이를 갱신인접한 vertex가 최단 경로에 이미 존재하면, 이전 경로 길이와 비교, 작으면 수정, 크면 무시그래프 내의 모든 vertex들..

I. 선택 정렬 (Selection Sort)의 개요가. 선택 정렬의 정의정렬이 안된 숫자들 중에서 최소 값을 선택하여 배열의 첫 번째 요소와 교환하는 정렬 기법 나. 삽입 정렬의 특징수행시간 복잡도 : O(n2)안정성을 만족하지 않음.  Ⅱ. 선택 정렬의 단계 및 사례가. 선택 정렬의 단계 (Pseudo Code)  나. 선택 정렬의 사례 public static int[] doSelectionSort(int[] arr){for (int i = 0; i {int index = i;for (int j = i + 1; j if (arr[j] index = j;int smallerNumber = arr[index];arr[index] = arr[i];arr[i] = smallerNumber;}return a..

I. 신장트리 (Spanning Tree)의 개요가. 신장 트리의 정의모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프 최소신장트리의 정의정점 간 가중치(cost)의 합이 최소인 신장 트리 Ⅱ. 최소신장트리 알고리즘가. Prim의 알고리즘 * 시작점 기반 최소 가중치* 정점마다 edge 검사* 우선순위 큐 기반 구현임의의 vertex를 선택, 신장 트리의 루트 노드로 삽입선택된 vertex와 인접 vertex들 사이의 edge 가중치 검사최소 가중치를 가지는 edge를 선택해당 edge로 두 정점을 연결했을 때, cycle이 발생하면 버리고, 그렇지 않으면 신장트리에 삽입선택된 edge는 edge리스트에서 제거edge리스트에 더 이상의 edge가 없을 때까지 2~5번 반복voi..

I. 기수 정렬 (Radix Sort)의 개요가. 기수 정렬의 정의레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법 나. 기수 정렬의 특징O (n log2 n) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법시간 복잡도 : O(kn) k : 버킷 수정렬 레코드 타입 제한 Ⅱ. 기수 정렬의 개념 및 사례가. 기수 정렬의 개념  나. 기수 정렬 사례 (Sorting a sequence of 4-bit integers) 코드 구현 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public void Radix_Sort(int[] data){int maxsize = getMaxlength(data..

I. 퀵 정렬 (Quick Sort)의 개요가. 퀵 정렬의 정의Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘 나. 퀵 정렬의 특징분할과 정복 기반재귀호출 구조정렬을 위한 별도의 스택이 필요수행시간 복잡도: O(n·log2n) Ⅱ. 퀵 정렬의 단계 및 사례가. 퀵 정렬의 단계 정렬할 원소들의 집합에서 Pivot 값을 설정Pivot보다 큰 값은 오른쪽, 작은 값은 왼쪽분할된 집합의 크기가 1이 될 때까지 반복 나. 퀵 정렬의 사례 void quicksort(element list[], int left, int right) {int pivot, i, j; element temp;if(left i = left; j = right + 1;pivot = list[..

I. 버블 정렬 (Bubble Sort)의 개요가. 버블 정렬의 정의여러 개의 자료 중에서 서로 이웃하는 키 값을 두 개씩 비교하여 순서를 결정하는 정렬 방법 나. 버블 정렬의 특징간단하지만 느린 속도의 알고리즘flag를 통해 속도 개선 가능수행시간 복잡도: O(n2) Ⅱ. 버블 정렬의 단계 및 사례가. 버블 정렬의 단계 인접한 두 개의 키 값을 비교함.앞의 키 값이 뒤의 키 값보다 크면 교환더 이상 비교할 대상이 없을 때까지 처음부터 반복 나. 버블 정렬의 사례 /* list에 대한 기본 버블정렬 알고리즘 */void bubble_sort(element list[], int n) {int i, j;element next;for(i = n-1; i > 0; i--){for(j = 0; j if(list[..

I. 해시 탐색 (Hash Search)의 개요가. 해시 탐색 (Hash Search)의 정의해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘해시테이블(hash table) : 키 값을 저장하는 테이블버킷(bucket) : 해시될 키 값의 범위, 테이블의 크기슬롯(slot) : 한 개의 버킷에 저장될 키 값의 개수 나. 해시 탐색 (Hash Search)의 특징고정길이, One WayO(1)의 탐색 속도충돌처리 매커니즘 필요 Ⅱ. 해시 함수의 기법가. 해시 함수의 기법 구 분내 용mid-square식별자의 제곱 값의 가운데 값을 취함.division나머지 연산자(modulus, %)을 이용함.- 버킷 주소의 범위 : 0 ~ m-1- m값의 선택이 중요함. m을 소수(prime..