Computer Science/Data Structure

여러가지 해시 함수 (Hash Function) 제산 함수테이블크기 $ m $ 을 소수로 선택하고, 탐색키를 테이블크기로 나눈 나머지를 사용한다.폴딩 함수탐색키를 여러 부분으로 나눈 후, 이동 폴딩(shift folding) 또는 경계 폴딩(boundary folding) 방식으로 결합한다.중간제곱 함수탐색키를 제곱한 뒤, 결과의 중간 몇 개 비트를 추출하여 해시 주소로 사용한다.비트추출 함수탐색키를 이진수로 변환한 후, 임의의 위치에서 $ k $ 개의 비트를 선택해 해시 주소로 만든다.숫자 분석 방법탐색키의 편중되지 않는 숫자들을 적절히 조합하여 테이블크기에 맞는 주소를 생성한다. 충돌 (Collision) 서로 다른 탐색키를 갖는 항목들이 같은 해시 주소를 가진다면 문제가 생길 것이고, 이를 충돌이라..

해시테이블  해시테이블이랑 해시를 이용하여 키(key)에 대응되는 값(value)을 저장하는 자료구조이다. 키에 대응되는 값에 빠르게 접근하는 것이 특징인데, 이는 해시 함수(hash function)를 이용하여 키에 대응되는 해시 주소(hash address), 즉 인덱스(index)를 생성하고, 이 인덱스를 통해 배열(버켓, bucket)에 값을 저장하기 때문이다. 배열에 저장하기 때문에 임의접근(ramdom access)이 가능하고, 따라서 잘 만들어진 해시테이블에서 키를 이용하여 값에 접근하는 것의 시간복잡도는 $ \mathcal{O}(1) $ 이다.해시 함수를 이용하여 키를 테이블 인덱스로 바꾸는 것을 해싱이라 하는데, 이 해싱을 어떻게 할 것이냐가 해시테이블의 접근 성능을 판가름한다. 당연히 ..

2-3 트리  차수가 2 또는 3인 트리, 즉 하위 노드의 개수가 두 개 혹은 세 개인 트리이다. 2-노드라면 이진 탐색 트리처럼 한 개의 데이터와 두 개의 자식 노드를 가지고, 3-노드라면 두 개의 데이터와 세 개의 자식 노드를 가진다.왼쪽 서브 트리에 있는 데이터들은 모두 첫 번째 데이터보다 작은 값이고, 중간 서브 트리에 있는 값들은 모두 첫 번째 데이터보다 크고, 두 번째 데이터보다 작아야 한다. 오른쪽 서브 트리에 있는 값들은 두 번째 데이터보다 커야 한다. 즉 이진 탐색 트리와 유사하게 정렬되어 있어야 한다.즉 트리가 위와 같다면 왼쪽 서브 트리의 값은 모두 $ k $ 보다 작고, 오른쪽 서브 트리의 값은 모두 $k $ 보다 크다.트리가 위와 같다면 왼쪽 서브 트리의 값은 $ k_1 $ 보다 ..

균형 이진 탐색 트리  이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조를 가지는데, 이진 탐색의 대상은 배열이므로 삽입과 삭제가 비효율적이지만 이진 탐색 트리에서 삽입과 삭제는 효율적이다. 단 이진 탐색 트리는 불균형인 경우 탐색의 시간복잡도가 $ \mathcal{O}(n) $ 이 되는 단점이 있다.이를 이진 탐색과 마찬가지로 효율적으로 탐색하기 위해서는 트리가 균형 트리여야 한다. 즉 이진 트리이면서 이진 탐색과 마찬가지로 왼쪽 서브트리 값이 노드 값보다 작게, 오른쪽 서브트리 값이 노드 값보다 크게 오도록 하며, 균형잡혀 있다면균형 이진 탐색 트리이다.간선의 수, 높이 등은 이진 트리(링크)의 속성을 일부 따른다. 노드가 $ n $ 개일 때 간선은 $ n -1 $ 개이고, 높이는..

보간 탐색  정렬된 리스트에서 탐색 범위를 줄여나가며 탐색하는 방식인데, 이진 탐색은 그냥 중앙을 탐색 위치로 지정하고 비교했다면 보간 탐색은 아래와 같은 공식을 이용해서 탐색 위치를 결정한다. 즉 이진 탐색이 균등 분할하였다면 보간 탐색은 불균등 분할하여 탐색한다.$$ \dfrac{\text{key} - \text{list}[\text{low}]}{\text{list}[\text{high}] - \text{list}[\text{low}]} \times (\text{high} - \text{low}) + \text{low} $$예를 들어 설명한다면 1400페이지의 전화번호부에서 하정우라는 이름을 찾는다고 해보자. 성에 ㅎ 이 들어가니까 당연히 중앙을 보는 것보다 1300페이지쯤부터 찾아보는 것이 효율적일..

순차 탐색  말 그대로 순차적으로 탐색하는 방법이다. 주어진 리스트의 시작부터 끝까지 찾으려는 값인 탐색키와 비교하면서, 탐색키와 같으면 반환, 다르면 다음 값을 탐색한다. 정렬되지 않은 경우 최선의 방법일 수 있다.값이 존재한다면 평균 비교 횟수는 $ (n+1) / 2 $ 이고, 값이 존재하지 않는다면 $ n $ 으로 시간복잡도는 $ \mathcal{O} (n) $ 이다.조금 개선된 순환 탐색 방법으로는 탐색 대상 리스트의 끝에 탐색키를 삽입하고 탐색키와 같은 값을 찾을 때까지 탐색한 후 탐색된 값의 인덱스가 삽입한 리스트의 인덱스라면 탐색 실패로 처리하는 방법이 있다. 구현 | C int sequential_search(int list[], int key, int low, int high) { ..

기수 정렬  여러 정렬들이 각 값을 비교한 후 알맞은 위치를 찾아가는 것과 다르게 어떤 정렬들은 값을 비교하지 않고 정렬한다. 기수 정렬이 대표적인 예시이다.사용하는 진법에 맞게 버킷을 만들고, 버킷에 차례대로 넣고, 작은 순서대로 꺼내면 정렬이 된다. 한자리 수들로 이루어진 리스트를 정렬하는 경우 버킷에 넣다 빼는 것을 한번만 하면 되지만, 두자리 수가 있다면 두번, 세자리 수가 있다면 세번 넣었다 빼야한다. 즉 리스트의 길이에 큰 영향을 받는 다른 정렬 방식과 다르게 리스트 내 최대값의 자리수에 영향을 더 많이 받는다는 특징이 있다. 예시 예를 들어 위와 같은 리스트를 정렬한다고 해보자. 먼저 아래와 같이 버킷을 만들어주어야 한다.가장 낮은 1의 자리를 기준으로 버킷에 차례로 담아준다.$$ \vdot..

병합 정렬   리스트를 균등하게 분할하고, 병합하면서 정렬하는 방법이다. 분할 정복 알고리즘의 대표적 예시 중 하나이다. 합병 정렬이라고도 한다.정렬은 데이터를 크기가 1이 될때까지 분할하고 다시 병합하면서 일어난다. 병합할 때 분할된 왼쪽 부분 리스트와 오른쪽 부분 리스트의 첫번째 값부터 차례대로 읽으면서 작은 값을 임의의 리스트에 넣어 정렬하는 것이다. 그렇게 병합이 된다면, 다시 상위의 부분 리스트와 병합하여 정렬하고, 다시 상위의 부분 리스트와 병합하여 정렬하여 최종적으로 분할된 모든 리스트를 병합하면 정렬이 끝난다. 이때 분할에서 재귀가 사용된다.새로운 리스트를 만들어서 병합 과정에서 사용하기 때문에 별도의 메모리 공간이 필요하고, 각 분할을 재귀로 구현해야하기 때문에 스택 메모리도 많이 사용한..

힙 정렬  최소 힙이나 최대 힙을 이용하는 정렬 방법이다. 최소 힙이나 최대 힙에 삽입한 후에 루트노드부터 삭제하면서 추출하면 정렬이 된다.힙을 구현하는 것이 귀찮을 뿐 힙이 구현되어 있다면 간편하게 구현할 수 있는 정렬 방법이고, 시간복잡도도 삽입에서 $ \mathcal{O}(\log_2 n) $, 삭제에서 $ \mathcal{O} (\log_2 n) $ 인데, 각 원소마다 삽입 삭제가 일어나므로 $ \mathcal{O} (n \log_2 n) $ 의 시간복잡도를 가지기 때문에 준수한 정렬 방법이다.힙과 관련된 내용은 링크를 참고하면 된다. 구현 | C void heap_sort(int list[], int n) { Heap heap; init(&heap); for (int i = 0;..

퀵 정렬  정렬을 사용할 때 일반적인 상황에서 가장 우수한 정렬 방법 중 하나이다. 분할정복법을 활용하는데, 리스트를 두개의 부분리스트로 비균등 분할하고 임시 정렬한 후 다시 분할하는 방법으로 정렬한다.피벗, 즉 축을 정해서 축을 기준으로 피벗보다 작은 값과 피벗보다 큰 값으로 분할하고 다시 그렇게 분할된 리스트에서 피벗을 설정하고 그 피벗을 기준으로 작은 값과 큰 값으로 분할하고, 다시 그렇게 분할된 리스트에서... 반복하여 정렬하는 방식이다. 왼쪽부터 오른쪽으로의 탐색이 하나, 오른쪽에서 왼쪽으로의 탐색이 하나 있어 만약 왼쪽에서 오른쪽으로 이동하다가 피벗보다 큰 값을 만나면 멈추고, 오른쪽에서 왼쪽으로 이동하다가 피벗보다 작은 값을 만나면 멈춘다. 두개 모두 멈추면 두 값을 교환하고, 다시 반복한다..