기수정렬 (Radix Sort) 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. ■ 정렬 방식 1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다. 2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다. 3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다. 4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다. 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다. 먼저..

[알고리즘] 알고리즘의 설계와 분석 - 시간 복잡도와 점근성능 1. 알고리즘 설계 기법 주어진 문제, 속성, 조건 등에 따라 매우 다양한 알고리즘이 존재할 수 있다. 따라서 일반적이고 범용적인 알고리즘 설계 기법은 존재하지 않지만 그 중 대표적인 설계 기법 세 가지를 꼽으면 다음과 같다. 분할 정복 방법(Divide-and-Conquer) 동적 프로그래밍 방법(Dynamic Programming) 욕심쟁이 방법(Greedy) 따라서 알고리즘을 공부하며 위 세 가지 설계 기법은 꼭 알아둬야 할것이다. 2. 알고리즘의 효율성 분석 알고리즘의 효율성 분석은 알고리즘 수행에 필요한 메모리 양과 수행 시간을 계산하는 것이다. 메모리 양 → 공간 복잡도(Space Complexity) = 정적 공간 + 동적 공간 ..