정렬의 종류별 알고리즘에 대해 정리할 때, 기수 정렬의 시간복잡도는 O(N)이 나왔었다. 그런데 일반적으로 정렬의 시간 복잡도는 O(N log N) 으로 알려져있다. 어떻게 기수 정렬은 O(N) 시간에 정렬을 할 수 있었을까? 그리고 왜 일반적으로 정렬의 시간 복잡도는 O(N log N) 으로 알려져 있는 걸까? 한번 O(n log n) 시간으로 고정되어있는 merge sort 의 comparison 과정을 tree로 표현해보자. a, b, c, d 라는 4개의 데이터에 대해 merge sort 를 수행하면, 반씩 쪼개다가 merge 하는 과정에서 비교를 수행한다. 이때 비교를 통해 정렬을 수행하는 모든 경우의 수를 comparison tree 로 그려보자. 제일 먼저 비교가 일어나는 부분은 a, b 이..
방식의 비교횟수와 쓰기 횟수를 비교해보고자 한다. 병합 정렬 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 ..
Binary Search 이분 탐색은 어떤 정렬된 데이터에 대해 특정 값을 찾을 때, 반씩 나누어 탐색하여 log 시간에 데이터를 찾는 알고리즘이다. 사이즈 n 의 다음과 같은 배열이 있다고 해보자. K1 K 이면, 찾는 값은 Km 기준 왼쪽에 있다. 따라서 u = Km - 1 으로 설정한다. ..
자료구조와 탐색 시간 지금까지 자료구조를 정리하면서 주요하게 다뤘던 내용 중 하나는 바로 "탐색" 이었다. 그리고 원하는 자료를 탐색하기 위해 수행한 가장 근본적인 동작은 바로 키를 비교하는 것이었다. 어떤 키가 다른 키와 같은지 다른지, 혹은 큰 지 작은 지를 비교하여 원하는 값을 탐색해내갔다. 여기 3글자 알파벳 소문자로 이루어진 이름과 4개의 숫자 쌍을 저장하는 간단한 주소록 프로그램이 있다. 그리고 이 주소록 프로그램에서 주소록 정보를 BST를 이용해 저장한다고 해보자. 만약 1000개의 주소록 데이터를 BST에 저장한다면, 최적의 경우 BST의 높이는 log(1000) 이므로 대략 10이라고 할 수 있고, 최악의 경우의 높이는 대략 1000이 될 것이다. 또 평균적으로는 1000개의 데이터를 B..
지난 글에서는 우선순위 큐와 이를 효율적으로 구현하기 위한 자료구조인 Heap 에 대해 정리하여 보았다. 이번 글에서는 한번 파이썬의 Heapq 를 뜯어보고자 한다. 뜯어보는 방법은 간단하다. 파이썬의 heap 모듈인 heapq 를 선언하고, ctrl 키를 누르고 클릭하면, 해당 모듈의 코드를 읽어볼 수 있다. Heap 개념 설명 코드 상단부에는 이렇게 heapq 모듈에 대한 설명과 사용 방법이 소개되어 있다. 위에 정의를 보면 우선순위큐를 heap queue 알고리즘이라고도 표현하는 것을 볼 수 있다. 파이썬의 공식 모듈에서 정의한 Heap은 모든 k 에 대해 a[k]
우선순위 큐 우선순위 큐는 우선순위를 가지는 아이템들을 가지는 큐이다. 일반적인 큐와 마찬가지로 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이라는 값..
