외부 정렬 (External Sort) 메인 메모리(main memory)인 램에 전체 데이터를 올릴 수 없다면 보조 메모리(auxiliary memory)인 하드 디스크, SSD 등에서 일부 데이터만을 메인 메모리에 가져와 정렬해야 한다. 이를 외부 정렬이라 한다. 앞으로 메인 메모리는 메모리, 보조 메모리는 디스크라 하겠다. 일부 데이터만을 가져올 수 있기 때문에 한 번에 데이터 정렬이 불가능하고, 여러번 메모리와 디스크를 오가며 정렬해야 하고, 따라서 이 경우 비교 횟수 보다는 읽고 쓰는 시간, 즉 I/O 횟수가 더 중요하게 작용한다. 따라서 외부 정렬에서 시간복잡도 기준은 I/O 횟수이다.외부 정렬을 앞서 말한대로 외부에서 데이터를 불러와서 정렬하는 정렬 단계(sort phase)와 이를 다시 합..

최소 최대 선택 (Minimum and Maximum Selection) 가장 간단하게 배열에서 최대값과 최소값을 찾는 방법은 모든 값을 비교하면서 크면, 혹은 작으면 선택하고, 아니면 넘기는 방식으로, 배열의 크기가 $n$ 이라 할 때 최대값 혹은 최소값을 찾을 때 $O(n)$ 의 시간복잡도를 요구한다.그러나 만약 최대값과 최소값을 한번에 찾으려고 한다면 이를 두 번 반복해야 할텐데 한번에 두 값씩 가져와서 비교하는 방식으로 이를 효율적으로 만들 수 있다. 배열에서 두 값을 가져오고, 이를 큰 값과 작은 값으로 나누고, 큰 값은 기존 최대값과, 작은 값은 기존 최소값과 비교하며 업데이트하는 것이다.int* find_min_max(int list[], int n) { int min = lis..

Sorting Algorithm 정렬 알고리즘은 elements의 list를 받아 재배열하는 것으로 다양하게 응용 가능하여 많은 알고리즘의 핵심 하위 루틴(core subroutine)으로 사용된다. 이러한 정렬 알고리즘은 크게 세 가지 측면에서 평가된다. 하나는 시간복잡도(time complexity), 또 하나는 공간복잡도(space complexity), 마지막 하나는 안정성(stability)이다.시간복잡도는 말 그대로 시간에 대한 측면으로 연산이 얼마나 이뤄이지는가에 대한 것이다. 보통 최악의 경우, 최상의 경우, 평균적인 경우로 나눠 확인하며 빅오, 빅오메가, 빅세타 등 표기법을 사용한다.공간복잡도는 메모리 사용 측면인데, 이를 빅오, 빅오메가, 빅세타 등 표기법으로 나타내기도 하지만, 제자리..

알고리즘 주어진 값 또는 값 집합을 입력(input)으로 받아 다른 값 또는 값의 집합을 출력(output)으로 생성하는 잘 정의된 계산 절차이다. 즉 알고리즘을 구성하기 위해서는 입력(input)과 출력(output)이 명확하게 정의되어야 한다. 알고리즘을 통해 입력부터 출력까지의 과정을 설명할 수 있다. 일종의 문제 해결 지침으로 생각할 수도 있다.바람직한 알고리즘은 명확해야 하고, 이해하기 쉬워야 하며, 간결해야 한다. 과도한 기호 표기는 명확성을 저해할 수 있기 때문에 지양된다. 다양한 표현 방법이 있지만, 명확성을 해치지 않는 한 자연어를 사용하는 것도 가능하다. 가장 중요한 것은 알고리즘은 효율적이어야 한다는 것이다. 동일한 문제를 해결하는 알고리즘이라도 실행 시간 차이가 수백만배까지 날 수 ..

여러가지 해시 함수 (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) { ..