기수정렬(Radix Sort)

CLRS INTRODUCTION TO ALGORITHMS/기초 2023. 3. 10. 02:34

기수정렬은 데이터를 자릿수 기준으로 나누어서 정렬을 수행합니다. 예를 들어, 10진수의 경우 각 자릿수는 0부터 9까지의 숫자 중 하나입니다. 따라서, 10진수 데이터를 기수정렬할 때는 0부터 9까지의 숫자를 각 자릿수로 사용하여 정렬을 수행합니다. 기수정렬의 구체적인 과정은 다음과 같습니다. 가장 작은 자릿수부터 가장 큰 자릿수까지 반복적으로 정렬을 수행합니다. 각 자릿수별로 데이터를 정렬하기 위해, 해당 자릿수의 값에 따라 버킷에 데이터를 넣습니다. 버킷에 있는 데이터를 순서대로 꺼내서 다시 배열에 넣습니다. 이때, 버킷에 들어있는 데이터의 순서는 유지됩니다. 가장 큰 자릿수까지 반복하면, 정렬이 완료됩니다. 기수정렬은 안정적인 정렬 알고리즘이며, 데이터의 크기와 무관하게 일정한 시간복잡도 O(d *..

소수 판별 에라토스테네스

CLRS INTRODUCTION TO ALGORITHMS/기초 2020. 11. 19. 01:09

소수의 판별은 약수의 개수로 생각해본다 만약 for문을 사용해 25의 약수를 구하려면 1부터 차례대로 나머지 연산자 % 를 이용해서 나머지가 0이 되는 숫자가 나오면 약수의 개수 변수에 카운팅을 한다. int prime; int div; for(div=0; (div*div)

삽입 정렬과 루프 불변성에 대해

CLRS INTRODUCTION TO ALGORITHMS/기초 2020. 10. 30. 02:05

이 모든 내용은 상위 카테고리의 책에서 발췌했습니다. 개인 공부용으로 작성하는 자료입니다. 문제가 될 시 삭제하겠습니다. 삽입정렬의 문제를 풀기 위해 다음과 같이 정의한다. 입력:n개 수들의 수열 출력:a`1