공부한 내용 기록하기 공부한 내용 기록하기

1. 버킷 정렬이란?버킷 정렬(Bucket Sort)은 데이터를 여러 개의 버킷(bucket)으로 나누어 정렬하는 비교 기반이 아닌 정렬 알고리즘이다. 각 버킷은 일정한 범위를 가지며, 데이터가 해당 범위에 따라 버킷에 배정된 후 개별적으로 정렬되고, 이후 병합되어 최종적으로 정렬된 배열을 얻는다.이 알고리즘은 입력 데이터가 고르게 분포된 경우 매우 효율적으로 동작하며, 평균적으로 O(n + k)의 시간 복잡도를 가진다. 일반적으로 삽입 정렬, 병합 정렬 또는 퀵 정렬을 보조적으로 사용하여 개별 버킷을 정렬한다.2. 버킷 정렬의 동작 원리버킷 정렬은 다음과 같은 과정을 거쳐 데이터를 정렬한다.2.1 정렬 과정입력 배열의 최댓값과 최솟값을 찾는다.범위를 기반으로 여러 개의 버킷을 생성한다.각 요소를 해당하..

1. 기수 정렬이란?기수 정렬(Radix Sort)은 정수를 자릿수별로 비교하여 정렬하는 비 비교 기반 정렬 알고리즘이다. 숫자의 각 자리(1의 자리, 10의 자리, 100의 자리 등)를 기준으로 여러 번 정렬을 수행하며, 일반적으로 계수 정렬(Counting Sort)을 보조적으로 사용하여 안정적인 정렬을 수행한다.기수 정렬은 O(nk)의 시간 복잡도를 가지며, k는 숫자의 최대 자릿수를 의미한다. 데이터의 크기 범위가 크지만 자릿수가 제한된 경우 매우 효율적으로 동작한다.2. 기수 정렬의 동작 원리기수 정렬은 가장 낮은 자릿수부터 시작하여 높은 자릿수로 이동하며 정렬하는 방식으로 수행된다.2.1 정렬 과정입력 배열에서 최댓값을 찾아 자릿수의 개수를 확인한다.1의 자리부터 시작하여 각 자릿수에 대해 정..

1. 계수 정렬이란?계수 정렬(Counting Sort)은 정수 데이터의 빈도를 기반으로 정렬하는 알고리즘으로, 비교 기반 정렬 알고리즘(퀵 정렬, 병합 정렬 등)과 달리 비교 연산을 수행하지 않는다. 특정한 범위 내의 정수 데이터를 빠르게 정렬할 수 있어 O(n) 시간 복잡도를 가진다.2. 계수 정렬의 동작 원리계수 정렬은 데이터의 크기를 기준으로 카운트 배열을 만들어 원소의 등장 횟수를 기록한 후, 이를 활용하여 정렬된 배열을 구성하는 방식으로 동작한다.2.1 정렬 과정입력 데이터 중 최댓값을 찾는다.최댓값을 기준으로 크기가 (max + 1)인 카운트 배열을 생성하고, 각 숫자의 등장 횟수를 기록한다.누적 합을 계산하여 각 숫자의 최종 위치를 결정한다.카운트 배열의 각 요소를 이전 요소의 값과 누적하..

1. 힙 정렬이란?힙 정렬(Heap Sort)은 "힙(Heap)" 자료구조를 활용하여 데이터를 정렬하는 비교 기반 정렬 알고리즘이다. 힙은 완전 이진 트리의 특성을 가지며, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나눌 수 있다. 힙 정렬은 평균 및 최악의 경우 O(n log n)의 성능을 보장하며, 추가적인 메모리 공간을 거의 사용하지 않는 효율적인 정렬 알고리즘이다.2. 힙 정렬의 동작 원리힙 정렬은 다음과 같은 단계로 동작한다.2.1 정렬 과정주어진 배열을 힙 자료구조로 변환한다 (Heapify 과정).최대 힙을 사용하여 가장 큰 요소를 배열의 끝으로 이동시킨다.힙 크기를 줄이고, 다시 힙을 재정렬(Heapify)하여 최대값을 루트로 유지한다.위 과정을 반복하여 배열이 완전히 정렬..

1. 병합 정렬이란?병합 정렬(Merge Sort)은 "분할 정복(Divide and Conquer)" 기법을 활용하여 리스트를 정렬하는 효율적인 알고리즘이다. 리스트를 반으로 나누고, 각각을 정렬한 뒤 병합하는 방식으로 동작한다. 시간 복잡도가 O(n log n)으로 일정하여 안정적인 성능을 제공한다.2. 병합 정렬의 동작 원리병합 정렬은 다음과 같은 과정을 거쳐 데이터를 정렬한다.2.1 정렬 과정배열을 두 개의 하위 배열로 분할한다.각 하위 배열을 재귀적으로 병합 정렬을 수행하여 정렬한다.정렬된 두 배열을 하나로 병합하여 최종 정렬을 수행한다.2.2 예제 코드 (Java)public class MergeSort { // 병합 정렬 메서드 public static void mergeSort(..

1. 퀵 정렬이란?퀵 정렬(Quick Sort)은 "분할 정복(Divide and Conquer)" 기법을 활용하여 리스트를 정렬하는 효율적인 알고리즘이다. 평균적으로 O(n log n)의 성능을 가지며, 대부분의 경우 매우 빠르게 동작하기 때문에 실무에서 널리 사용된다.2. 퀵 정렬의 동작 원리퀵 정렬은 피벗(Pivot) 요소를 선택하고, 피벗보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 이동시키는 분할 과정을 반복하여 정렬을 수행한다.2.1 정렬 과정배열에서 피벗(Pivot)을 선택한다.피벗을 기준으로 작은 값과 큰 값을 좌우로 분할(Partitioning)한다.분할된 두 개의 하위 배열을 재귀적으로 정렬한다.모든 하위 배열이 정렬되면 최종적으로 정렬이 완료된다.2.2 Partition 함수 설명..

1. 선택 정렬이란?선택 정렬(Selection Sort)은 정렬되지 않은 부분에서 가장 작은 요소를 찾아 정렬된 부분의 끝과 교환하는 방식으로 동작하는 비교 기반 정렬 알고리즘이다. 구현이 간단하지만, 수행 속도가 느려 큰 데이터셋에서는 비효율적이다.2. 선택 정렬의 동작 원리선택 정렬은 배열을 순차적으로 탐색하며, 각 단계에서 가장 작은 요소를 찾아 적절한 위치에 배치하는 방식으로 정렬을 수행한다.2.1 정렬 과정배열에서 최소값을 찾는다.최소값을 배열의 첫 번째 요소와 교환한다.정렬된 부분을 제외하고, 나머지 배열에서 위 과정을 반복한다.배열 전체가 정렬될 때까지 위 과정을 반복한다.2.2 예제 코드 (Java)public class SelectionSort { // 선택 정렬 메서드 pu..

1. 삽입 정렬이란?삽입 정렬(Insertion Sort)은 정렬되지 않은 요소를 하나씩 선택하여 올바른 위치에 삽입하는 방식으로 동작하는 정렬 알고리즘이다. 카드를 정렬하는 방식과 유사하며, 작은 데이터셋에서 효과적인 성능을 발휘한다.2. 삽입 정렬의 동작 원리삽입 정렬은 배열을 순차적으로 탐색하며, 현재 요소를 정렬된 부분에 적절한 위치로 삽입하는 방식으로 동작한다.2.1 정렬 과정두 번째 요소부터 시작하여 앞의 요소들과 비교한다.적절한 위치를 찾을 때까지 요소를 왼쪽으로 이동시킨다.올바른 위치를 찾으면 삽입한다.배열의 끝까지 이 과정을 반복한다.2.2 예제 코드 (Java)public class InsertionSort { // 삽입 정렬 메서드 public static void inse..