컴퓨터 이론66 43. 해싱 오버플로우 처리 기법 오버플로우를 처리하기 위해서는 다양한 방법이 존재한다. 체인법 체인법은 충돌이 발생한 버킷에 연결리스트를 사용하여 데이터를 저장하는 방법이다. void insertData(HashTable* ht, int key) { int index = hashFunction(key, ht->size); // 새로운 노드 생성 Node* newNode = (Node*)malloc(sizeof(Node)); newNode->key = key; newNode->next = NULL; // 버킷에 노드 추가 if (ht->table[index] == NULL) { ht->table[index] = newNode; } else { Node* curr = ht->table[index]; while (curr->next != N.. 2023. 6. 15. 41. 탐색 (2) 피보나치 탐색 피보나치 탐색은 피보나치 수열을 이용하는 탐색 방법이다. int fiboSearch(int arr[], int n, int key){ int fib2 = 0, fib1 = 1, fib = fib2 + fib1; int i, offset = -1; while (fib 1){ i = (offset + fib2) key){ fib = fib2; fib1 =.. 2023. 5. 27. 40. 탐색 (1) 배열에서 원하는 값을 찾는 방법에는 여러 방법이 있다. 대표적으로는 배열의 0번 인덱스에서부터 마지막 인덱스까지 모든 배열을 확인하는 방법이 있다. 이처럼 이번에는 다양한 탐색 알고리즘에 대해서 알아보려고 한다. 순차 탐색 순차 탐색은 모든 탐색 중 가장 기본적인 탐색 방법이다. 배열의 첫 인덱스의 데이터에서부터 모든 데이터를 하나씩 확인하는 방법이다. int linearSearch(int arr[], int n, int key){ int i; for(i=0;i 2023. 5. 25. 39. AOE AOE란? AOV와는 다르게 간선이 작업을 표현하며, 가중치는 작업의 소요 시간을 의미한다. 정점은 작업의 완료를 나타내는 사건을 의미한다. AOE 네트워크는 선후행 관계를 가진 작업 또는 활동들을 그래프로 표현한 것이다. 작업 간의 선후행 관계와 소요 시간을 통해 프로젝트의 전체 소요 시간을 계산할 수 있다. AOE 네트워크는 프로젝트 관리에서 크리티컬 패스를 분석하는 데에 사용된다. 크리티컬 패스는 전체 프로젝트 소요 시간을 결정하는 가장 긴 경로를 의미하며, 작업등 간의 선후행 관계와 소요 시간을 고려하여 도출된다. 크리티컬 패스 상의 작업들은 프로젝트 완료 기한을 결정하는 핵심적인 작업들로 간주된다. AOE 구현 #include #include #include #define MAX_VERTICES.. 2023. 5. 19. 38. AOV AOV란? AOV란 Activity On Vertex, 즉 정점이 Activity, 작업을 나타내고, 간선이 작업 간의 우선순위 관계를 나타내는 방향 그래프이다. 즉 1 -> 2 -> 3으로 이루어진 작업이 있다면 작업 3을 수행하기 위해서는 2가 우선 수행되어야 하고, 작업 2를 수행하기 위해서는 1이 우선 수행되어야 한다. 위상 정렬 작업들간의 선후 관계를 유지하면서 모든 작업을 나열하는 알고리즘이다. 1. 모든 정점들의 진입 차수를 계산한다. 2. 진입 차수가 0인 모든 정점들을 Stack에 넣는다. 3. 스택에서 정점 k를 꺼내 k와 인접한 모든 정점에 대해서 진입차수를 1 감소시킨다. 4. 스택에 정점이 없을 때까지 2 ~ 3 과정을 반복한다. 위상 정렬 구현 #include #include #.. 2023. 5. 18. 37. Floyd-Warshall 알고리즘 플로이드-워셜 알고리즘이란? 지금까지의 최단거리 알고리즘은 하나의 시작 노드에서 모든 노드까지 가는 최단거리를 구한 것이다. 플로이드-워셜 알고리즘은 모든 노드 쌍 사이의 최단거리를 찾는 알고리즘이다. 벨만-포드 알고리즘과 마찬가지로 음의 가중치를 가지는 그래프에도 적용이 가능하다. 플로이드-워셜 알고리즘 기본 아이디어 1. 노드의 개수를 N이라고 할 때, N X N 크기의 2차원 배열 dist를 생성하여 최단거리를 저장한다. dist[i][j]는 노드 i에서 노드 j로 가는 최단거리를 의미한다. 2. 초기 단계에서 dist 배열을 입력 그래프의 가중치로 초기화한다. 만약 직접 가는 길이 없다면 INF로 설정한다. 3. 세 개의 반목문을 사용하여 모든 노드 쌍 사이의 최단거리를 찾는다. 4. dist[i.. 2023. 5. 17. 이전 1 2 3 4 5 6 7 8 ··· 11 다음