CS

14.5 개방 주소법 ● 충돌과 오버플로우 충돌: 서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상 오버플로우: 충돌이 발생했을 때 해당 해시 주소에 더 이상 빈 버킷이 남아있지 않아 항목을 저장할 수 없는 현상 오버플로우 해결하는 2가지 해결책 1. 개방주소법: 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장 2, 체이닝: 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조 변경 14.5절에서는 개방 주소법에 대해 다루고 14.6절에서 체이닝을 다룬다. ● 선형 조사법 조사(probing): 해시테이블에서 비어있는 공간 찾기 선형조사법: ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어있는지 확인 후 비어있다면 삽입, 비어있지 않다면 ht[k+2] 확인 조..

14.1 해싱이란? ● 해싱: key에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 직접 접근하는 탐색 - 해시 테이블: 키에 대한 연산에 의해 직접 접근이 가능한 구조 - 컴바일러가 사용하는 심볼 테이블, 철자 검사기, 데이터베이스 등에서 활용 - O(1)의 시간안에 탐색을 마칠 수 있음 14.2 추상 자료형 사전 ● 사전: (키, 값)의 쌍으로, 키와 관련된 값을 동시에 저장하는 자료구조. map이나 table로도 불림 키(key): 사전의 단어처럼 항목과 항목을 구별시켜주는 것 값(value): 단어의 설명에 해당 - 항목들의 위치는 상관없으며 키만 알고 있으면 항목에 접근하고 삭제할 수 있다. - 리스트는 위치에 의해 관리되는 자료구조인 반면, 사전은 오직 키에 ..

01 (3) 02 05(a) 03 (2) 04 100,00,000 경사트리일 경우, 최악의 경우는 O(n) 05(b) 06 07 생략 08 이진 탐색 트리는 정렬되어있지않은 배열을 못받기 때문에 AVL tree를 활용해 정렬시킨 후 해당 트리를 중위순회하며 arr[] 배열에 담아서 정렬한 숫자를 출력하였다. // 위는 AVL Tree code int arr[6]; int k=0; void inorder(AVLNode *root){ if(root !=NULL){ inorder(root->left); arr[k++] = root->key; inorder(root->right); } } int main(){ AVLNode *root = NULL; root = insert(root,30); root = inse..

13.4 이진 탐색 트리 이진 탐색은 자료들이 배열에 저장되어 있어 삽입과 삭제가 힘들다는 단점 존재 이진 탐색 트리는 삽입, 삭제가 빈번한 상황에서 사용 - 이진 탐색 트리는 트리가 균형 트리 일 때 O(log2n)의 시간 복잡도를, 균형 트리가 아닐 때는 최악의 경우 O(n)의 시간복잡도를 가짐 알고리즘 최악 평균 탐색 삽입 탐색 삽입 순차 탐색(정렬x) N N N/2 N 이진 탐색(정렬o) logN N logN N/2 이진 탐색 트리 N N logN logN 모든 항목이 균일하게 탐색된다는 가정 하에 평균 비교 횟수를 비교 좌측 트리와 같은 편향된 경사 트리는 (1+2+3+4+5+6+7)/7 = 4 우측 트리와 같은 균형트리는 (1+2+2+3+3+3+3)/7 = 2.4 따라서 이진 탐색 트리에서는 ..

13.1 탐색이란? ● 탐색: 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것 - 탐색을 위해 사용되는 자료구조: 배열, 연결 리스트, 트리, 그래프 등 - 탐색 성능 향상을 위해 이진 탐색 트리와 같은 보다 진보된 방법으로 자료를 저장 및 탐색 항목: 탐색의 단위 (ex. 숫자, 구조체 ..) 탐색키: 항목과 항목을 구별시켜 주는 키 13.2 정렬되지 않은 배열에서의 탐색 ● 순차 탐색(sequential search): 하아목의 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 - 탐색 방법 중 가장 간단하고 직접적임 - 탐색의 범위는 low에서 high까지 함수의 매개변수로 주어짐 - 탐색에 성공하면 그 항목이 발견된 위치의 인덱스를 반환..

01 4 02 2 03 3 04 3 05 (1) 7 4 9 6 3 8 7 5 3 4 9 6 7 8 7 5 3 4 5 6 7 8 7 9 3 4 5 6 7 7 8 9 (2) 7 4 9 6 3 8 7 5 4 7 9 6 3 8 7 5 4 6 7 9 3 8 7 5 3 4 6 7 9 8 7 5 3 4 6 7 8 9 7 5 3 4 6 7 7 8 9 5 3 4 5 6 7 7 8 9 (3) 7 4 9 6 3 8 7 5 4 7 6 3 8 7 5 9 4 6 3 7 7 5 8 9 4 3 6 7 5 7 8 9 3 4 6 5 7 7 8 9 3 4 5 6 7 7 8 9 (4) 7 4 9 6 3 8 7 5 3 4 7 5 7 8 9 6 3 4 7 5 7 6 9 8 3 4 5 6 7 7 8 9 06 (1) 71 49 92 55 38 8..

12.6 합병 정렬 ● 합병 정렬의 개념 분할정복: 문제를 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 문제가 충분히 작지 않아 해결이 어렵다면 분할 정복 방법을 연속으로 재적용하여 더 작게 만들어 해결 합병 정렬의 단계 1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할 2. 정복(Conquer): 부분 배열 정렬. 부분 배열의 크기가 충분히 작지 않으면 순환 호출로 분할 정복 재적용 3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합 작은 문제인 부분 배열에 대해서도 다시 합병 정렬을 순환적으로 적용하면 부분 배열을 정렬할 수 있다. ● 합병 정렬의 알고리즘 void merge_sort(int list[],int le..

12.1 정렬이란? ● 정렬: 대상을 크기순으로 오름차순이나 내림차순으로 나열하는 것(키 값을 기준으로) - 레코드: 정렬시켜야 할 대상 - 필드: 레코드의 구성단위 ex) 학생이라는 레코드의 필드는 이름, 학번, 주소, 등 - 키(key): 레코드와 레코드를 식별해 주는 역할을 하는 필드 ex) 학번 각 상황에서 가장 효율적인 정렬 알고리즘을 선택하여야 함 효율성의 기준 = 비교 연산의 횟수 + 이동 연산의 횟수 ● 효율성과 복잡성 단순하지만 비효율적인 정렬 알고리즘 (자료 개수가 적을 때 사용) - 삽입 정렬, 선택 정렬, 버블 정렬 등 복잡하지만 효율적인 정렬 알고리즘 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬, 권정열 등 ● 내부와 외부 정렬 내부 정렬 - 정렬 전 모든 데이터가 메인 메모..

04 void prim(GraphType *g, int s){ int i,u,v; for(u=0; un; u++){ distance[u] = INF; } distance[s]=0; for(i=0; in; i++){ u = get_min_vertex(g->n); selected[u] = TRUE; // 04 문제 프린트문 시작 printf("selected[]= "); for(int j=0;jn;j++){ printf("%d ",selected[j]); } printf("\n"); printf("distance[]= "); for(int j=0;jn;j++){ printf("%d ",distance[j]); } // 04 문제 프린트문 종료 if(distance[u]==INF) return; printf(..

11.4 최단 경로 ● 최단 경로(shortest path): 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로 - DIjkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다. - Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다. 가중치는 가중치 인접 행렬에 저장돼 있고 u와 v사이에 간선이 없다면 INF가 저장된다. * 인접행렬에서는 간선이 없으면 인접 행렬의 값이 0인 반면 가중치 인접 행렬에서는 실제 가중치가 0일 수 있어서 0의 값이 간선이 없음을 나타내지 못한다. 따라서 INF가 간선이 없음을 나타낸다. 11.5 Dijkstra의 최단 경로 알고리즘 ●DIjkstra 알고리즘: 하나의 시작 정점으로부터 모든 다른 정..