홍카나의 공부방

기수 정렬이라고 번역되는 Radix Sort, 자릿수 정렬이라고 생각하면 이해가 더 쉬울 것이다. 기수 정렬은 말 그대로 자릿수와 정수를 이용해서 정렬을 하는데, 정수로 이루어진 배열을 정렬할 때 유독 사용하기 좋다. 한 번 살펴보자.  0부터 9를 담을 수 있는 큐 10개를 만든다. 여기서 큐를 만든 것은, 먼저 들어간 원소를 쉽게 제거할 수 있는 FIFO 자료구조를 사용한 것이다. 큐 대신에 리스트나 덱을 이용해도 구현은 할 수 있겠지만, 큐를 예시로 들어보겠다. 입력으로 예시 삼을 리스트가 [170, 45, 75, 90, 2, 802, 2, 66] 라고 가정하자. 여기서 각 정수들의 1의 자릿수만 살펴보면 다음과 같다. [0, 5, 5, 0, 2, 2, 2, 6] 1의 자릿수의 숫자에 맞게 해당 숫..

합병 정렬은 분할 정복(devide & conquer) 방법에 속하는 정렬 알고리즘이다. 문제를 쪼개서, 작게 나누고, 해결하는 방법이다. 어느 컴퓨터공학과든 자료 구조 시간에 이 머지 소트는 무조건 배우고 간다고 생각할 정도로 기본적인 알고리즘이라고 본다. 머지소트는 다음의 단계를 거친다.1. 정렬되지 않은 리스트를 원소를 1개 가지는 N 개의 서브리스트로 나눈다. (N = 리스트의 길이). 나눌 때는 절반씩 쪼개게 된다.2. 서브 리스트를 합치면서 정렬을 하고, 원소를 N개 가지는 1개의 리스트까지 합병한다.   합병 과정에서 어떻게 정렬하는지 살펴보면, 아래와 같이 합병 과정 중인 2개의 서브리스트가 있을 때 로직은 다음과 같다.  1. i와 J가 기리키는 숫자의 대소관계를 비교하고, 작은 숫자를 ..

Heap 힙(Heap)은 가장 큰 값 혹은 가장 작은 값을 바로 꺼낼 수 있도록 만든 자료구조다. 여기서 단순한 정렬 알고리즘처럼 전체 key 값에 대한 오름차순이나 내림차순 정렬이 목표가 아니라는 점을 유의하자. 스택, 큐와 내부 구조를 비교한다면 아래와 같다.스택 : LIFO큐 : FIFO힙 : 가장 큰 값(Maxheap), 가장 작은 값(Minheap)힙은 필요한 만큼만 정렬이 되어 있다. 여기서 필요한 만큼이라 하면, 본래의 목적인 가장 큰 값 찾기를 지킬 수 있는 만큼만 정렬이 되어 있다는 것이다. 그래서 정렬이 주 목적이라면 다른 자료구조를 이용할 것을 권장한다. 구현은 Maxheap으로 진행한다. Minheap의 경우 Maxheap 구현을 약간만 바꿔주면 구현할 수 있다. 그리고 Tree 구..