Programming/DS Concept 썸네일형 리스트형 해싱의 성능 분석 해싱의 성능 분석 해싱의 시간 복잡도는 이다. 그러나 이것은 충돌이 전혀 일어나지 않는 상황에서만 가능하다. 따라서 실제 해싱의 탐색 연산은 보다는 느려지게 된다. 해싱의 성능을 분석하기 위해 해시 테이블이 얼마나 채워져 있는지를 나타내것을 적재 밀도(loading density) 또는 적재 비율(loading factor) 라 한다. * n = 저장된 항목의 개수, M = 해싱 테이블의 버켓의 개수 가 0 이면 해시 테이블은 비어있다. 의 최댓값은 충동 해결 방법에 따라 달라지는데, 선형 조사법에서는 테이블이 가득하면 모든 버켓에 하나의 항목이 저장되므로 1이 된다. 체인법에서는 저장할 수 있는 항목의 수가 해시 테이블의 크기를 넘어설 수 있기 때문에 는 최댓값을 가지지 않는다. 기존의 연구 결과들을 .. 더보기 이차 조사법, 이중 해싱법, 체이닝 이차 조사법이차 조사법(quadratic probing) 은 선형 조사법과 유사하지만 충돌 방생 시 다음에 조사 할 위치를 다음 식에 의하여 결정한다. (h(k) + i*i) mod M for i = 0,1, ... , M-1 따라서 조사되는 위치는 다음과 같다. h(k), h(k) + 1, h(k) + 4, h(k) + 9, ..... mod M 여기서 주의할 것은 모든 위치를 조사하게 만들려면 여전히 테이블 크기는 소수여야 한다는 점이다. 이 방법은 선형 조사법에서의 문제점인 군집화 현상을 크게 완화시킬 수 있다. 이 방법도 2차 집중 문제를 일으킬 수 있지만 1차 집중처럼 심각한 것은 아니다. 2차 집중의 이유는 동일한 위치로 사상되는 여러 탐색키들이 같은 순서에 의하여 빈 버켓을 조사하기 때문이다.. 더보기 해싱의 오버플로우 처리 방법 해싱의 오버플로우 처리 방법 해싱에서 오버플로우를 잘 처리하는 것은 매우 중요하다. 이러한 오버플로우의 처리 방법은 다음의 두 가지로 나눌 수 있다. (1) 선형 조사법(linear probing) : 충돌이 일어나면 해시 테이블의 다른 위치를 찾아 항목을 저장한다. (2) 체이닝(chaining) : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경한다. 선형 조사법 선형 조사법(linear probing) 은 해싱 함수로 구한 버켓에 빈 슬롯이 없으면 그 다음 버켓에서 빈 슬롯이 있는지를 찾는 방법이다. 이때 비어 있는 공간을 찾는 것을 조사(probing) 이라고 하는데, 여러 가지의 조사 방법이 가능하다. 만약 ht[k] 에서 충돌이 방생했다고 하자. 선형.. 더보기 균형 이진 탐색 트리 균형 이진 탐색 트리 맵은 이진 탐색 트리로도 구현할 수 있다. 이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조로 탐색에 걸리는 시간도 로 동일하다. 그렇다면 이들의 차이는 무엇일까? 답은 자료의 삽입과 삭제의 용이성에 있다. 이진 탐색에서 자료는 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉, 맵에 자료를 삽입하거나 삭제할 때 불필요한 항목들의 많은 이동이 필요하다. 반면에 맵을 이진 탐색 트리로 구현하면 시간에 삽입과 삭제가 가능하다. 따라서 삽입과 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다. 이진 탐색 트리는 만약 균형 트리이면 의 탐색 연산 시간 복잡도를 갖는다. 그러나 삽입과 삭제 연산이 이진 탐색 트리를 유지시키기는 하지만 균형 트리를.. 더보기 퀵 정렬 라이브러리 함수의 사용 함수의 원형void qsort(void* base,size_t num,size_t width,int (*compare)(const void *, const void *)); 함수의 파라미터 설명base : 배열의 시작 주소 num : 배열 요소의 개수width : 배열 요소 하나의 크기(바이트 단위)compare : 비교 함수. 포인터를 통하여 두개의 요소를 비교하여 비교 결과를 정수로 반환한다. 사용자가 제공하여야 됨. #include #include #include // 두 수를 비교해 오름차순으로 정렬되도록 하는 함수int compareAs(const void *arg1, const void *arg2) {return (*(double *)arg1 > *(double *)arg2) ? 1 :(*(d.. 더보기 DataStructure - Prim 의 MST 알고리즘 Prim 의 MST 알고리즘 Prim의 알고리즘은 하나의 정점에서부터 시작하여 트리를 단계적으로 확장해나가는 방법이다. 처음에는 시작 정점많이 트리에 포함된다. 다음으로 지금까지 만들어진 트리에 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 n-1ㅐ의 간선을 가질 때까지 계속된다. Prim의 알고리즘을 자연어로 나타내면 알고리즘은 아래와 같다. | Prim의 최소 비용 신장 트리 알고리즘 Prim( ) 1. 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.2. 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v 를 선택한다.3. 이 정점 v와 이때의 간선을 트리에 추가한다.4. 모든 정점이 삽입될 때 까지 2번으로 이동한.. 더보기 DataStructure - 신장 트리, Kruskal 의 MST 알고리즘, 위상 정렬 신장 트리 신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리다. 신장 트리도 트리의 일종이므로 모든 정점들이 연결되어 있고 사이클이 없어야 한다. 신장트리는 그래프에 있는 n개의 정점을 정확히(n-1)개의 간선으로 연결하게 된다. 신장 트리를 찾기위해 기피 우선 탐색이나 너비 우선 탐색을 이용할 수 있는데, 하나의 그래프에는 많은 신장 트리가 가능한 것에 유의하라. 신장트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선들만 모으면 만들 수 있다. 최소 비용 신장 트리 최소 비용 신장 트리(MST : minimum spanning tree) 란 어떤 그래프의 신장 트리들 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 최소 비용 신장 트리를 구하는 방법에는.. 더보기 DataStructure - 힙(heap) 힙 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말한다.힙(heap)은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 힙은 일종의 반 정렬 상태를 유지한다. 즉, 요소들이 완전히 정렬된 것은 아니지만 전혀 정렬되지 않은 것도 아닌 상태를 이용해 우선순위 큐를 구현한다. 힙의 시간 복잡도는 삽입과 삭제 모두 으로 다른 방법보다 상당히 유리하다. 여기서 다시 한 번 과 은 큰 차이가 있다는 것을 유념해야 한다. 만약 n 이 1024이고 알고리즘이 1024초가 걸린다면 알고리즘은 10초에 불과하다.표현 방법 삽입 삭제 순서 없는 배열 순서 없는 연결 리스트 정렬된 배열 정렬된 열결 리스트 힙 더보기 이전 1 2 다음