방식의 비교횟수와 쓰기 횟수를 비교해보고자 한다. 병합 정렬 merge_sort() 함수의 호출시, 기존 배열을 복사해서 넣어놓고, 카운팅할 비교횟수와 데이터 쓰기 횟수를 초기화한다. mergeSort() 라는 재귀용 함수를 호출한다. 받은 배열을 반씩 나눠서 재귀적으로 mergeSort 를 호출하며, mergeSort 로 반씩 정렬된 결과를 다시 합쳐서 정렬할 merge 함수도 호출한다. 실질적인 정렬이 수행되는 merge 함수다. 먼저 반씩 정렬된 배열을 다른 배열에 복사해서 옮겨둔다. merge sort 를 배열롤 구현할 때 반드시 수행해야 하는 작업이기에, 이는 데이터 쓰기 횟수에 포함시켜서 카운팅했다. 그리고 기존 입력된 배열을 복사한 배열을 반씩 나눠 탐색하면서 작은값부터 채워나간다. 이 과정..
그림과 같이 100만개의 랜덤 성생된 정수가 있다. 이 정수를 각 정렬 방법으로 정렬해보려고 한다. (100만개를 N^2 시간에 정렬하면 시간이 오래 걸려서, 실제로는 100, 200, ..., 900 단위로만 정렬해 볼 것이다.) 정렬을 수행하면서, 비교는 몇번 일어나는지, 정렬을 하기 위해, 기존 배열에 (또는 새로 생성한 배열에) 데이터를 쓰는 행위를 몇번이나 하는지 횟수를 세보고자 한다. 이를 위해 먼저 100만개의 정수가 담긴 데이터를 ' ' 기준으로 끊어 배열에 저장한다. 그리고 각 정렬을 수행한다. 정렬은 사이즈가 100, 200, 300, ..., 900 인 상황을 매번 수행해보면서, 그 때의 비교횟수와 데이터 쓰기 횟수를 카운팅한다. 차례대로 정렬을 구현하고, 횟수를 카운팅한 결과를 출력..
정렬은 큰 사이즈의 작업에 대해 컴퓨터가 자주 수행하는 동작 중 하나다. 이번 글에서는 5가지 정렬 방법에 대해 간단하게 정리하고자 한다. 선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) 은 말 그대로 정렬 기준에 맞는 값을 선택해서 정렬하는 알고리즘이다. 선택 정렬은 In-Place 방식으로, O(n^2) 시간에 수행된다. 알고리즘은 다음과 같다. 1. 정렬된 결과의 0번째 원소를 결정하려고 한다. 2. 0번째원소를 1번째 원소부터 N-1번째 원소까지 하나하나 비교해보면서 그 중 제일 작은 원소와 swap 한다. 3. 이번엔 1번째 원소를 결정하려고 한다. 4. 1번째 원소를 2번째 원소부터 N-1 번째 원소까지 하나하나 비교해보면서 그 중 제일 작은 원소와 swap ..
자료구조와 탐색 시간 지금까지 자료구조를 정리하면서 주요하게 다뤘던 내용 중 하나는 바로 "탐색" 이었다. 그리고 원하는 자료를 탐색하기 위해 수행한 가장 근본적인 동작은 바로 키를 비교하는 것이었다. 어떤 키가 다른 키와 같은지 다른지, 혹은 큰 지 작은 지를 비교하여 원하는 값을 탐색해내갔다. 여기 3글자 알파벳 소문자로 이루어진 이름과 4개의 숫자 쌍을 저장하는 간단한 주소록 프로그램이 있다. 그리고 이 주소록 프로그램에서 주소록 정보를 BST를 이용해 저장한다고 해보자. 만약 1000개의 주소록 데이터를 BST에 저장한다면, 최적의 경우 BST의 높이는 log(1000) 이므로 대략 10이라고 할 수 있고, 최악의 경우의 높이는 대략 1000이 될 것이다. 또 평균적으로는 1000개의 데이터를 B..
우선순위 큐 우선순위 큐는 우선순위를 가지는 아이템들을 가지는 큐이다. 일반적인 큐와 마찬가지로 push(), pop() 두가지 기능을 제공하지만, 우선순위 큐는 데이터를 저장할 때 단순히 데이터의 값 뿐만 아니라 데이터의 우선순위를 같이 저장하는 점이 다르다. 그래서 우선순위 큐에는 push(x, p) 와 같은 형태로 데이터를 저장한다. x 는 저장하는 데이터, p 는 저장하는 데이터의 우선순위이다. 그리고 pop을 할 때는 우선순위가 높은 데이터부터 나온다. 우선순위 큐의 구현 우선순위 큐의 개념은 간단하다. 그런데 우선순위 큐의 구현은 간단하지 않다. 만약 일반적인 큐를 구현할 때처럼 연결 리스트를 사용한다면 어떨까? 데이터를 pop 할 때, 우선순위가 높은 순부터 뽑아야 하므로 아래 2가지 방법중..
지난 글에서는 이진 탐색트리의 개념과 Search, Add, Delete 의 구현에 대해 정리하였다. 이번 글에서는 BST의 핵심인 '탐색' 과 탐색 시간에 대해 좀 더 깊게 정리해보자. BST의 탐색 시간 모든 BST의 기능 중에서 제일 중요한 것은 BST 의 이름에도 들어있는 '탐색' 기능이다. 탐색 시간이 얼마나 걸리는지 ( 탐색을 위해 비교를 몇 번이나 하는지) 는 어떻게 측정할까? 답은 정확하게 BST 의 노드 중 찾으려는 노드의 depth + 1 (level + 1) 이다. 더보기 [트리에서 Depth, Height, Level ] Depth = 루트 노드의 depth를 0 으로 정의할 때, 자식 노드의 depth는 부모 노드의 depth + 1 이다. Level = Depth 와 같다. de..
이진 탐색 트리 (Binary Search Tree, BST) 는 노드가 정렬되어 있어 탐색을 수행할 수 있는 이진 트리를 말한다. 각 노드는 여러개의 필드로 이루어진 데이터를 가지고 있다고 가정한다. 데이터 중에서 탐색을 하기 위해 사용되는 데이터를 '키' 라고 한다. node v 의 키를 key(v) 라고 정의하면, BST 는 모든 노드 u 에 대해서 아래를 만족하는 이진트리이다. (1) 만약 v 가 u 의 왼쪽 서브트리에 있다면 key(v) key(u) 이다. 등호는 좌, 우 둘 중 하나 어디든 들어가도 되지만, 왼쪽에 들어간 것으로 생각하자. 이 정의를 통해 이진 탐색 트리는 매우 효율적으로 원하는 key 를 탐색할 수 있다. 이제 이렇게 생긴 BST가 있다고 가정해보자. 이 트리에서 3이라는 값..
지난 글에서는 트리와 이진트리, 그리고 이진 트리를 만들 수 있는 가짓수인 카탈란 수에 대해서 정리하였다. 이번 글에서는 이진 트리를 순회하는 3가지 방법을 정리해보고자 한다. 사람에 관점에서는 이진트리의 전체적인 모습이 보이기 때문에 특정 노드를 찾을 때 전체 이진트리에서 특정 노드를 바로 딱 보면 쉽게 알 수 있다. (글로벌 뷰) 하지만 컴퓨터 입장에서 이진트리를 탐색할 때는, 연결리스트 때와 비슷하게, 현재 자신이 보고 있는 노드 T와, 그 T의 ITEM(T), 왼쪽 노드 LEFT(T) , 오른쪽 노드 RIGHT(T) 만 본다. (로컬뷰) 이런 로컬 뷰가 재귀적으로 반복되기 때문에, 이진트리를 탐색할 때는 재귀를 이용하게 되는데, 이진 트리를 재귀적으로 탐색하는 방법에는 3가지가 있다. Preord..
지난 글에서는 연결리스트가 사용하는 메모리 공간을 어떻게 관리하는지 그 구현을 C언어로 직접 해보았다. 이번 글에서는 트리와 이진트리의 개념을 정리해보고자 한다. 트리 트리는 아래와 같이 정의된다. a tree is a finite set T of nodes such that 1) T has one special node called root 2) the remaining nodes are partitioned into m disjoint sets T1, T2, ... Tm, and each of these sets is turn to a tree. wee call them subtrees of T 트리는 '루트' 라고 불리는 특별한 하나의 노드를 가지고 있고, 나머지 노드들은 m 개의 서브트리를 이루는..
지난 글에서는 연결리스트를 이용해 스택과 큐를 구현하였다. 이번 글에서는 연결리스트를 이용하는 과정에서 new(), free() 기능을 사용했는데, 이 기능을 직접 구현해본다. 사실 직접 구현이라고 해서 나도 처음엔 메모리를 직접 다루는 거창한 걸 기대했는데, 그런건 아니다. 그냥 배열을 이용해서 전체 memory pool 을 세팅해두고, 그 세팅된 pool 내 메모리를 주고 받고 하는 방식이다. 메모리 풀은 연결리스트 노드의 데이터 형태로 배열에 세팅해두고, 이를 스택처럼 활용하여 메모리를 주고 받는다. 메모리 풀은 이런 구조로 존재한다. 만약 new 함수로 메모리 공간을 요청하면 top이 가리키는 노드를 제공해준다. 제공을 마친 모습이다. 제공된 메모리는 연결리스트에서 자유롭게 Item 부분에도 값을..
