1. 계수 정렬 앞에서 포스팅한 것 중 제일 빠른 알고리즘을 고르자면 O(Nlog₂N)의 속도를 가지는 퀵 정렬, 병합 정렬, 힙 정렬이 있었다. 하지만 이번 포스팅에서는 이 세 개의 정렬보다 더 빠른 속도 O(N)의 속도를 가지는 계수 정렬에 대해서 포스팅하려고 한다. 단, 아래와 같은 조건이 주어졌을 경우다. 5 4 3 2 1 1 1 1 3 4 5 5 2 2 2 다음과 같은 5이하의 원소를 가진 배열의 원소들을 오름차순으로 정렬하시오 2 . 동작 순서 동작 순서는 다음과 같이 간단하다. 1에서 5까지의 원소의 개수를 카운팅한다. 카운팅한 개수만큼 원소들을 나열한다. 끝. 그림을 이용해서 설명을 해보도록 하겠다. 밑의 배열을 오름차순으로 정렬하려고 한다. 5 이하의 모든 자연수의 개수를 세기위해 5라는..

힙 정렬(Heap Sort)은 힙 생성 알고리즘를 이용하여 정렬하는 방법이다. 힙 생성 알고리즘은 특정한 노드의 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 또한 위치를 바꾼 후에도 자식이 존재하는 경우, 비교 연산을 수행하여 더 큰 자식과 자신의 위치를 바꾸어야한다. 따라서 최대 힙의 경우, 루트 노드의 원소는 가장 큰 수가 된다. 힙 생성 알고리즘에 대해서는 이전에 포스팅한 적이 있다. 그래서 이번 포스팅에서는 따로 설명하지는 않겠다. 그런데 힙 생성 알고리즘의 시간 복잡도는 몇 일까? 정답은 $$ O(nlog_{2}N) $$ 이다. 왜냐하면 한 번 자식노드가 증가할 때마다 노드의 개수가 2배씩 증가하기 때문이다. 예를 들어 데이터가 1024개라면 대략 10번 정도만 내려가면 된다...

1. 힙 (Heap) 힙은 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조다. 키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙이라고 하고, 키 값이 작은 노드를 찾기 위한 힙을 최소 힙이라고 한다. 최대 힙은 부모노드의 키 값 > 자식노드의 키 값의 관계를 가지는 완전 이진 트리다. 따라서 최대 힙의 루트 노드는 가장 큰 값이 된다. 하지만 최소 힙은 부모노드의 키 값 ..

1. 이진 탐색 트리란? 이진 탐색 트리란 이진트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것을 말한다. 이진 탐색 트리의 특징은 다음과 같다. 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브트리에 있는 원소의 크기는 그 루트의 키보다 작다. 오른쪽 서브트리에 있는 원소의 키는 그 루트의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리다. 이번 포스팅에서 다룰 것은 이진 탐색 트리에 대한 간략한 정의, 탐색, 삽입, 삭제 연산이다. 이진 트리의 순회에 대해서는 이전에 포스팅을 했으니 참고하길 바란다. 2. 탐색 연산 탐색은 항상 루트에서 시작된다. 따라서 먼저 키값과 루트 노드의 키값을 비교한다. 비교 결과는 다음의 세 가지 중 하나가 될 것이다. (키값 x =..

1. 트리 연결리스트, 스택, 큐는 자료들이 선의 형태로 쭉 나열되어 있는 구조를 가지고 있다. 이를 선형 자료구조라고 한다. 반대로 자료구조가 선의 형태로 나열되지 않는 구조를 비선형 자료구조라고 한다. 여기서 트리는 비선형 자료구조 중에서 자료들 간에 계층적인 구조를 이루고 있다. 가계도를 떠올리면 쉽다. [그림 1] 가계도를 보면 준식는 태성, 형준이라는 두 명의 자식이 있고 태성 또한, 민경, 지영이라는 두 명의 자식이 있다. 이렇듯 가계도에서 가족 구성원을 연결하는 선은 부모-자식 관계를 나타낸다는 것을 알 수 있다. 그리고 쭉 올라가면 준식이라는 조상을 만날 수 있다. 이제 가계도를 트리 구조로 바꾸면 다음과 같다. 구조적으로 딱히 가계도와 다르지 않다. 간단하게 용어설명을 하겠다. A, B,..

1. 순차 선형 리스트 나는 C, 파이썬, 자바 그리고 자바스크립트를 배웠다. 이 네 개의 언어를 배우면서 느낀 점이 있다면, 여러 개의 데이터를 한꺼번에 저장하는 방법을 배울 때 가정 먼저 배열을 배운다는 것이다. 이 배열을 자료구조에서는 순차 선형 리스트라고 한다. 순차 선형 리스트는 논리적이고 물리적인 순서가 같아서 원소의 위치에 대한 접근성이 쉽다는 장점이 있다. 하지만, 삽입, 삭제 연산 후에 원소들을 이동시키는 추가적인 작업과 시간이 필요하다는 것이 단점이다. 또한, 순차 선형 리스트는 삽입 삭제 연산이 엄청나게 많을 경우, 원소들의 이동작업도 그에 따라 비례한다. 이는 오버헤드 증가를 초래하여 성능상의 문제를 일으킬 수 있기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 갖고..