nomad-programmer

이진 탐색 트리는 '탐색에 효율적인 자료구조'이다 그리고 '이진 트리'의 일종이다. 이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문이다. 그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가? 예를 들어 연결 리스트에 10억 개의 데이터가 저장되어 있다고 가정해보자. 그리고 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정해보자. 이는 분명 유용한 정보이다. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다. 반면 이진 트리의 경우에는 위치를 알고 있다면, 즉 데이터에 이르는 길을 알고 있다면 루트 ..

탐색의 이해 탐색은 '데이터를 찾는 방법'이다. 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 이유는 다음과 같다. "효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 된다. 그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'를 우선 고민해야 한다." 그런데 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다. 때문에 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여있다. 정렬도 탐색을 목적으로 하는 경우가 대부분일 만큼 탐색은 자료구조에서, 컴퓨터 공학에서 매우 중요한 위치를 차지하고 있다. 보간 탐색(Interpolation Search) 정렬되지 않은 대상을 기반으로 하는 탐색 : 순차 탐색 정렬된 대상을 기반으로 하는 탐색 : 이진 탐색 이 중에서 이진 탐색은 중앙에 위치..

기수 정렬은 정렬순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다. 비교연산은 정렬 알고리즘의 핵심이라 할 수 있다. 특히 두 데이터 간의 정렬순서상 우선순위를 판단하기 위한 비교연산은 핵심중의 핵심이다. 때문에 모든 정렬 알고리즘들은 이 연산을 포함하고 있다. 뿐만 아니라 알고리즘의 복잡도도 이 연산을 근거로 판단해왔다. 그런데 이런 유형의 비교연산을 하지 않고서도 정렬을 할 수 있는 것이 "기수 정렬"이다. 그리고 정렬 알고리즘의 이론상 성능의 한계는 O(nlog2n)으로 알려져 있는데, 기수 정렬은 이러한 한계를 넘어설 수 있는 유일한 알고리즘이다. 물론 이렇게 좋은 점만 있는 것은 아니다. 다른 알고리즘에는 없는 단점도 있다. 그것은 바로 '적용할 수 있는 범위가 제한적'이라는 것이다. 예..

병합 정렬과 마찬가지로 '분할 정복(divide and conquer)'에 근거하여 만들어진 정렬 방법이다. 실제로 퀵 정렬 역시 정렬 대상을 반씩 줄여나가는 과정을 포함한다. 퀵 정렬은 그 이름이 의미하듯이 평균적으로 매우 빠른 정렬의 속도를 보이는 알고리즘이다. 위 그림에서는 퀵 정렬의 대상이 되는 배열을 보이고 있다. left : 정렬대상의 가장 왼쪽 지점을 가리키는 이름 right : 정렬대상의 가장 오른쪽 지점을 가리키는 이름 피벗(pivot)의 사전적 의미는 다음과 같다. pivot : 중심점, 중심축의 의미 즉 피벗은 정렬을 진행하는데 필요한 일종의 '기준'이라 할 수 있따. 때문에 정렬의 진해을 위해서는 피벗이라는 것을 진행해야 한다. low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가..

병합 정렬은 '분할 정복(divide and conquer)'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다. 분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 '분할(divide)'하여 '정보(conquer)'하는 방법을 말한다. 단 분할해서 정복했으니 정복한 후에는 '결합(combine)'의 과정을 거쳐야 한다. 즉 다음 3단계를 거치도록 알고리즘을 디자인 하는 것이 분할 정복법이다. 1단계 분할(Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다. 2단계 정복(Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다. 3단계 결합(Combine) : 분할해서 해결한 결과를 결합하여 마무리한다. 이 방법을 근거로 어떻게 병합 정렬 알고리즘이 디자인되었을까..