해슁에서의 충동해결(Collision Resolution)
이전글 - 해슁(Hashing) / 해쉬 알고리즘 / 해쉬 함수 충동 해결(Collision Resolution)에는 크게 두 가지 방법이 있다. 첫 번째는 체이닝(Chaining)으로 해쉬 테이블의 각 주소가 연결 리스트의 헤더 역활을 하고, 여기에 해당 주소로 들어오는 원소들이 연결 리스트(Linked List)로 매달린다. 두 번째는 개방 주소 방법인데, 체이닝처럼 추가 공간을 사용하지 않고 해쉬 테이블 안에서 충돌을 해결한다. 원래 들어갈 자리가 아니더라도 테이블의 다른 자리를 찾아 들어가게 된다. ① 체이닝(Chaining) 체이닝에서는 같은 주소로 해슁되는 원소를 모두 하나의 연결 리스트에 매달아 관리한다. 위 의 그림처럼 h(39) = h(13) = 0 인 경우 해쉬테이블의 0 인덱스는 39..
해슁(Hashing) / 해쉬 알고리즘 / 해쉬 함수
해쉬 테이블(Hash Tables) 일반적인 검색트리는 원소 하나를 저장하고 검색하는 데 평균적으로 의 시간이 걸리고, 최악의 경우 의 시간이 걸린다. 저장된 자료의 양에 상관없이 원소 하나를 저장·검색하는 데 항상 상수 시간에 가능하게 할 수 없는지 사람들은 요구하게 되었고, 이 꿈을 실현한 것이 해시 테이블이다. 해시 테이블은 자료의 저장·검색에 있어 극단적인 효율에 다다른 자료구조이다. 해시(Hash) 테이블은 원소의 값에 의해 결정되는 자료구조이다. 즉, 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자리를 찾는다. 해쉬 함수 임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시값을 계산한다. 해시값은 해시 함수에 의해 계산된다. 해시 함수는 키값을 입력으로 받아 해시..
힙정렬(Heap Sort)
힙정렬(Heap Sort)은 힙(Heap)이라는 특수한 자료구조를 사용하는 정렬 알고리즘이다. 힙은 최소힙(Minimum Heap)과 최대힙(Maximum Heap)이 있는데 값이 저장되는 방향만 반대일 뿐 성질은 똑같다. 우선 힙(heap)에 대해서 설명하면, 힙은 이진트리(Binary Tree)로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다(nearly complete binary tree). 힙은 최소힙, 최대힙에 따라 다음의 성질을 가지고 있다. 최소힙(minimum heap)의 성질각 노드의 값은 자신의 자식의 값보다 작다. 최대힙(maximum heap)의 성질각 노드의 값은 자신의 자식의 값보다 크다. 위의 그림은 최대힙(maximum heap)의 예를..
퀵정렬(Quick Sort)
퀵정렬(Quick Sort)는 평균적으로 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우(Worst-Case) Θ(n^2)의 시간복잡도를 가져 Θ(nlogn)의 시간복잡도를 가지는 병합정렬, 힙정렬보다 성능이 안좋아보일 수 있으나 평균적인 성능은 어떤 정렬에도 뒤떨어지지 않는다. 퀵정렬(Quick Sort)는 배열의 한 원소를 기준(피봇, pivot)으로 삼아 피봇보다 작은 수들은 피봇의 앞으로, 피봇보다 큰 수들은 피봇의 뒤로 보낸다. 정렬되지 않은 피봇의 좌우는 재귀적으로 문제를 해결하여 배열 전체가 정렬이 되도록 한다. 예를 들어 설명하면 다음과 같다. 이 예는 배열의 젤 뒷원소를 피봇으로 삼아 퀵정렬(Quick Sort)를 수행하는 경우이다. 피봇인 15보다 작은 수들..
병합정렬/합병정렬(Merge Sort)
병합정렬/합병정렬(Merge Sort)는 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈 다음 정렬해서 병합한다. 즉, 원래의 정렬 문제와 성격이 똑같고 단지 크기만 반으로 줄었을 뿐이다. 후반부에 대한 정렬도 마찬가지다. 병합정렬은 자신에 비해 크기가 반인 문제를 두개 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다. 위 그림의 예를 살펴보면 초기 배열 A = { 5, 2, 4, 7, 1, 3, 2, 6} 이다. 병합정렬의 전반부, 후반부 정렬이 재귀적으로 반복되면서 배열의 원소가 하나씩 남을때 까지 쪼개진다. 그리고 각각 병합을 하면서 정렬이..