이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종입니다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다. 예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능합니다. 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산복잡성이 발생합니다. 두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적입니다. 이진탐색트리는 다음과 같은 속성을 지니며 아래 그림과 같습니다. 완전이진트리이다. 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다. 각 노드의 오른쪽 서..

정렬 알고리즘 시간복잡도 비교 단순(구현 간단)하지만 비효율적인 방법 삽입 정렬, 선택 정렬, 버블 정렬 복잡하지만 효율적인 방법 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 선형 시간 알고리즘 명칭 실행시간 실행시간 예 linear time(선형시간) O(n) n

- 선형시간 정렬 알고리즘 : 계수 정렬 - 앞 장에서 설명한 정렬 알고리즘은 비교 연산을 통해서 정렬을 하는 방식을 취했다. 비교 연산은 두 개의 원소의 관계를 크고 작음에 따라 비교하여 판단하는 연산이다. 비교연산으로 정렬하는 방법은 아무리 빨라도 nlgn보다는 빠를 수가 없다. 하지만 비교를 하지 않는 방법으로 하면 이 보다 따른 시간으로 수행이 가능하다. 이런 방법으로 계수 정렬이 있다. 계수 정렬은 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. x라는 입력은 x보다 작은 원소의 개수가 I-1개라면 정렬 후에 I번째에 위치해야 한다. x보다 작은 원소의 개수는 원소를 개수를 세어서 확인할 수 있다. 계수 정렬에 대한 예를 한 번 들어보자. A라는 배열이 입력으로 들어왔다고 가정한다. A..

힙정렬은 시간복잡도가 nlogn 으로 퀵정렬과 병합(합병)정렬과 같은 시간복잡도를 가진 정렬 알고리즘이다. 하지만 병합정렬과는 다르게 추가적인 메모리가 필요하지않고, 항상 nlogn의 정렬 성능을 보여주기때문에 최악의 경우 n^2 의 성능을 보이는 퀵정렬보다 안정적인 성능을 보인다. 힙정렬은 힙의 구조에 대해 알고있으면 생각보다 간단한 정렬이다. 힙정렬을 알아보기전에 힙(Heap) 에 대해 간단히 알아보자. 힙(Heap) 힙 트리 라고도 하는 힙은 완전이진트리 형태의 자료구조이다. 완전이진트리 노드를 삽일할때 왼쪽부터 차례대로 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리) 위와같은 트리가 완전이진트리이며(각노드의 왼쪽부터 채워진 이진트리) 아래는 그냥 이진트리. 힙에는 최소힙과 최대힙이 있..

퀵 정렬(quick sort) 알고리즘의 개념 요약 ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다. 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(p..

합병 정렬(merge sort) 알고리즘의 개념 요약 ‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트..