자료구조 (26) 썸네일형 리스트형 Hash Table Chaining 구현 Hash Table의 Chaining을 구현 해보자 기존 Hash Table 에서 약간(?) 심화 과정으로써 Hash Table에서 Hash Key가 겹쳤을 경우를 처리하는 자료구조이다. 위와 같은 상황이 놓여졌을 때 Chaining으로 하여 값을 Insert 한다. Chaining은 Linked List로 구현하기 위해 Hash Table 구조체를 다음과 같이 수정하였다. typedef struct _storage { void *mem_slot_p; struct _storage *next_p; } Storage; typedef struct _hashTable { /* == hash table member == */ Storage **data_strge_pp; /* == hash table work fu.. Hash Table 구현 Hash Table을 구현해 보자 Hash Table 이란 자료를 저장하기 위한 여러가지 자료구조중 하나로 복잡도가 O(n) 이다. Hash Table을 대략 그림으로 표현 하면 다음과 같다. data 및 Hash key를 만드는 함수에 따라 Hash Key 가 중복 될수 있지만 추후 다루고 현재는 중복되지 않는다는 가정에 작업한다. Hash Table 에 자료를 저장할 변수는 void 형 이중 포인터로 한다. void로 한 이유는 저장 할 데이터 구조가 어떻게 저장하냐에 따라 저정할 데이터 구조가 매번 바뀌기 때문에 범용성을 위해 void 형을 사용 했고 저장하는 데이터 역시 데이터 자체를 저장하기 보다 데이터를 나타내는 포인터를 저장하기 위해 이중 포인터를 사용했다. 따라서 HashTable를 사용하.. AVL Tree 구현 AVL Tree를 구현해보자. AVL Tree는 이진 트리의 균형이 맞지 않을 때 탐색연산의 시간 복잡도가 O(log2n)아닌 O(n)에 가까운 시간 복잡도를 보이는데 이런 단점을 해결위한 트리중 하나이다. 위 그림을 봤을 때 왼쪽은 균형이 무너진 이진트리이고 오른쪽은 균형이 잡힌 이진트리이다. 5를 탐색한다고 했을 때 한눈에 봐도 성능차이가 난다는 것을 알 수 있다. AVL Tree는 균형이 무너졌는지 확인 후 균형을 맞추는 작업을 한다. 여기서 균형이 무너졌는지 확인 하는 방법은 균형 인수(Balance Factor)를 구하여 확인한다. 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 서브트리의 높이를 구하는 방법은 자식 노드를 가지고 있는 부모노드 의 갯수를 체크하여 높이를 확인한.. 이진탐색트리 Search 후 remove 구현 이진 탐색트리 삭제를 구현해보자 이진 탐색트리에서 search후 삭제를 할 때 다음 같은 상황이 있다. 1. 삭제할 노드의 자식 노드가 left 노드만 존재하는 경우 2. 삭제할 노드의 자식 노드가 right 노드만 존재 하는 경우 3. 삭제할 노드의 자식 노드가 양쪽 노드가 모두 존재하는 경우 4. 삭제할 노드의 자식 노드가 없는 경우 1. 삭제할 노드의 자식 노드가 left 노드만 존재하는 경우 위 그림에서 4의 자식노드는 left 노드만 있으므로 4를 삭제한다고 해보자 쉽게 판단 할 수 있듯이 4의 자식 노드를 8의 자식노드에 붙여 주면 끝이다. 4 노드를 삭제 후 8의 자식노드를 2에 연결 해주면 끝~!!! 2. 삭제할 노드의 자식 노드가 right 노드만 존재 하는 경우 삭제할 노드의 자식노드가.. 이진탐색트리 Insert, Search 구현 이진 탐색 트리를 구현해보자 이진 탐색 트리는 '이진 트리'에 '데이터의 저장 규칙'을 더해놓는 것이 '이진 탐색 트리'이다. 이진 탐색트리가 되기 위해서는 다음과 같은 조건이 필요하다. 1. 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다. 2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. 3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다. 4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 앞에 언급한 키(key)는 탐색의 조건이 될 수 있으며 이번에 구현할 코딩에서는 데이터가 곧 key 값이 된다. 위 조건을 만족하는 트리를 그림으로 표현 하면 다음과 같다 (윤성우의 자료구조 참조) 위 그림을 통해 보면 다음 수식이 어디서나 만족함을.. Radix 정렬 구현 기수 정렬을 구현해보자 기수 정렬의 가장 큰 특징은 "정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다" 기본적으로 정렬 알고리즘의 이론상 성능의 한계는 O(nlog2n)으로 알려져 있는데 기수 정렬은 이러한 한계를 넘어설 수 있는 유리한 알고리즘이다. 다만 기수정렬의 단점은 범위가 매우 제한 적이다. 위에서 말하는 단점, 즉 범위의 정확한 뜻은 '데이터의 길이' 이다. 왜 데이터의 길이가 문제인가 하면 저장하는 버퍼, 즉 버킷의 갯수의 영향을 미치며 데이터 길이에 따른 별도의 알고리즘이 들어가야 한다. 별도의 알고리즘이 들어가면서 까지 기수 정렬은 효율적이지 않기 때문에 실제 사용하는 자료구조에서는 기수정렬을 많이 사용하지 않는다. 다음 그림은 한자릿 수의 기수정렬을 보여준다. 원리는 간단.. Quick 정렬 구현 Quick 정렬을 구헌해보자 이전에 공부한 Merge Sort를 안다면 쉽게 공부할 수 있다. Quick 정렬 역시 Merge Sort와 마찬가지로 분할 정복(Divide and conquer)으로 근거하여 만든 정렬 방법이다. 다만 Merge Sort와 다른점은 Merge Sort는 균등하게 나누었다면 Quick Sort는 비균등하게 나눈다. Quick Sort에는 3가지 변수를 사용한다. 1. Pivot : 중심점 2. LeftIndex: Pivot을 제외한 제일 왼쪽 Index 3. RightIndex: Pivot을 제외한 제일 오른쪽 Index pivot을 제일 왼쪽으로 하면 다음 그림과 같이 변수가 잡힌다. Quick Sort 과정 1. left Index를 Pivot 보다 큰 값을 만날때 까지.. 병합 정렬 구현 (병합) #2 앞서 분열한 배열들을 정렬해보자 처음 들어간 배열은 1~ 8 으로 들어 갔으니 8 ~ 1 로 정렬 해본다 아래 그림은 정렬하는 과정을 나타내는 그림이다. 노란색 박스를 보자 일단 1, 2를 병합 하면서 정렬하여 2,1이 정렬되었고 3,4 역시 정렬 되어 4,3으로 정렬 되었다고 하자 첫번째 병합된 배열은 Start Index에서 End index가 Mid인 상황이고 두번째 병합된 배열은 Start Index가 mid+1 인 상황에서 End Index 까지 정렬 되어있는 상황이다. 이제 두 배열을 병합해보자 노란박스 안에 배열은 3개가 있고 다음과 같다. 1번째 배열은 이전에 정렬되어 올라온 첫번째 배열(2,1) 2번째 배열은 이전에 정렬되어 올라온 두번째 배열(4,3) 3번째 배열은 1,2배열을 병합한 .. 이전 1 2 3 4 다음
