728x90 반응형 전체 글46 계수 정렬(Counting Sort) - 정의 / 예시 코드 계수 정렬(Counting Sort)은 정수나 정수 형태의 자료에 대해 선형 시간 복잡도를 가지는 안정적인 정렬 알고리즘입니다. 기존의 비교 기반 정렬 알고리즘과는 달리 계수 정렬은 비교를 사용하지 않고, 정수의 개수를 세는 방식으로 동작합니다. 이를 통해 정렬할 자료에 대한 추가 정보를 이용하여 정렬을 수행하므로, 일반적인 경우에 매우 효율적입니다. 계수 정렬의 동작 방식은 다음과 같습니다. 1. 정렬할 정수 배열에서 최솟값과 최댓값을 찾습니다. 이를 통해 배열의 범위를 파악합니다. 2. 범위 내에서 각 정수의 등장 횟수를 세어 빈도수 배열(Count 배열)에 저장합니다. Count 배열의 인덱스는 정수 값이고, 해당 인덱스의 값은 해당 정수의 등장 횟수입니다. 3. Count 배열을 누적합으로 변환합.. 2023. 6. 4. 기수 정렬(Radix Sort) - 정의 / 예시 코드(C++) 기수 정렬(Radix Sort)은 비교 정렬 알고리즘이 아닌 정렬 알고리즘 중 하나로, 비교 대상의 특정한 속성을 이용하여 정렬하는 방법입니다. 기수 정렬은 숫자나 문자열과 같은 자료를 정렬하는 데에 주로 사용되며, 각 자릿수나 문자의 위치를 기준으로 정렬을 수행합니다. 기수 정렬의 동작 방식은 다음과 같습니다. 1. 가장 낮은 자릿수부터 시작하여 가장 높은 자릿수까지 반복적으로 정렬 작업을 수행합니다. 2. 각 자릿수를 기준으로 정렬하기 위해, 0부터 9까지의 버킷(또는 큐)을 생성합니다. 이 버킷은 해당 자릿수의 값을 가진 요소를 저장하는 용도로 사용됩니다. 3. 정렬할 자료를 순회하면서 각 요소의 해당 자릿수 값을 확인하고, 그에 맞는 버킷에 요소를 넣습니다. 예를 들어, 첫 번째 반복에서는 일의 .. 2023. 6. 3. 힙 정렬(Heap Sort) - 정의 / 예시 코드 힙 정렬(Heap Sort)은 힙 자료구조를 기반으로 동작하는 정렬 알고리즘입니다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성하여 배열을 정렬하는 방식으로 동작합니다. 힙 정렬은 주로 배열 기반의 힙 자료구조를 사용하여 구현됩니다. 아래는 힙 정렬의 동작 과정을 단계별로 설명한 것입니다. 1. 주어진 배열을 최대 힙 또는 최소 힙으로 구성합니다. 이 단계를 힙 구성(Heapify) 단계라고 합니다. 최대 힙을 구성하는 경우, 부모 노드는 항상 자식 노드보다 큰 값을 가지며, 최소 힙을 구성하는 경우에는 그 반대입니다. 2. 힙에서 최상단에 있는 노드(최대 힙의 경우 최댓값, 최소 힙의 경우 최솟값)를 꺼내어 배열의 마지막 위치로 이동시킵니다. 이 단계를 반복적으로 수행하면, 배열은.. 2023. 6. 2. 병합 정렬(Merge Sort) - 정의 / 예시 코드 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘을 사용하여 배열을 정렬하는 효율적인 알고리즘입니다. 배열을 반으로 나누고, 각 부분 배열을 재귀적으로 정렬한 후, 정렬된 부분 배열을 병합하여 최종적으로 정렬된 배열을 생성하는 방식으로 동작합니다. 아래는 병합 정렬의 동작 과정을 단계별로 설명한 것입니다. 1. 주어진 배열을 반으로 나눕니다. 이를 분할(Divide) 단계라고 합니다. 2. 각 부분 배열에 대해 재귀적으로 병합 정렬을 수행합니다. 부분 배열의 크기가 1 이하가 될 때까지 반복합니다. 3. 부분 배열을 정렬하고 나면, 정렬된 부분 배열을 병합(Merge)하여 크기가 더 큰 정렬된 부분 배열을 생성합니다. 4. 병합된 배열을 최종적으로 정렬된 배열로 반.. 2023. 6. 1. 퀵 정렬(Quick Sort) - 정의 / 예시 코드 퀵 정렬(Quick Sort)은 평균적으로 매우 효율적인 정렬 알고리즘 중 하나로 알려져 있습니다. 분할 정복(Divide and Conquer) 방식을 기반으로 동작하며, 배열을 작은 값의 부분 배열과 큰 값의 부분 배열로 분할하고 재귀적으로 정렬하는 방식입니다. 아래는 퀵 정렬의 동작 과정을 단계별로 설명한 것입니다. 1. 배열에서 하나의 원소를 기준으로 선택합니다. 이를 피벗(Pivot)이라고 합니다. 피벗은 보통 첫 번째 원소, 마지막 원소, 중간 원소 등으로 선택됩니다. 2. 피벗을 기준으로 배열을 두 부분으로 분할합니다. 피벗보다 작은 원소는 피벗의 왼쪽에 위치하고, 피벗보다 큰 원소는 피벗의 오른쪽에 위치하도록 배열을 재배치합니다. 이 단계를 피벗을 기준으로 분할하는 Partition 단계라.. 2023. 5. 31. 선택 정렬(Selection Sort) - 정의 / 예시 코드 선택 정렬(Selection Sort)은 간단하면서도 직관적인 정렬 알고리즘입니다. 주어진 배열에서 가장 작은(또는 가장 큰) 원소를 선택하여 정렬 순서에 맞게 앞으로 이동시키는 방식으로 동작합니다. 아래는 선택 정렬의 동작 과정을 단계별로 설명한 것입니다. 1. 주어진 배열에서 가장 작은(또는 가장 큰) 원소를 찾습니다. 2. 해당 원소를 정렬 순서에 맞게 배열의 첫 번째 위치(또는 마지막 위치)와 교환합니다. 3. 정렬된 부분과 정렬되지 않은 부분으로 배열을 나눕니다. 4. 정렬되지 않은 부분에서 다음으로 작은(또는 큰) 원소를 선택하여 해당 위치에 삽입합니다. 5. 위의 과정을 정렬되지 않은 부분의 원소가 모두 정렬될 때까지 반복합니다. 아래는 C++로 구현된 선택 정렬의 예시 코드입니다. 위의 예.. 2023. 5. 30. 삽입 정렬(Insertion Sort) - 정의 / 예시 코드 삽입 정렬(Insertion Sort)은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다. 아래는 삽입 정렬의 동작 과정을 단계별로 설명한 것입니다. 1. 주어진 배열을 순회합니다. 2. 배열의 첫 번째 원소는 이미 정렬되었다고 간주합니다. 3. 다음 원소부터 시작하여 정렬되지 않은 부분의 원소를 하나씩 선택합니다. 4. 선택한 원소를 정렬된 부분의 올바른 위치에 삽입합니다. - 선택한 원소를 정렬된 부분의 마지막 원소부터 비교하며, 적절한 위치를 찾아갑니다. - 선택한 원소보다 큰 값이 나올 때까지 이전 원소를 한 칸씩 오른쪽으로 이동시킵니다. - 적절한 위치를.. 2023. 5. 29. 버블 정렬(Bubble Short) - 정의 / 예시 코드 버블 정렬(Bubble Sort)은 간단하고 기본적인 정렬 알고리즘 중 하나입니다. 인접한 두 원소를 비교하여 필요에 따라 위치를 교환하는 방식으로 동작합니다. 버블 정렬은 원소의 크기를 비교하며 작은 원소를 앞쪽으로 이동시키는 "거품"이 위로 올라가는 것과 유사하다고 해서 버블 정렬이라는 이름이 붙었습니다. 아래는 버블 정렬의 동작 과정을 단계별로 설명한 것입니다. 1. 주어진 배열을 순회합니다. 2. 배열에서 현재 원소와 다음 원소를 비교합니다. 3. 현재 원소가 다음 원소보다 크다면, 두 원소의 위치를 교환합니다. 4. 배열의 끝까지 이동할 때까지 위의 과정을 반복합니다. 5. 1회 순회가 끝나면, 가장 큰 원소가 배열의 마지막에 위치하게 됩니다. 6. 2회째 순회에서는 마지막 원소를 제외하고 위의.. 2023. 5. 28. 이전 1 2 3 4 5 6 다음 728x90 반응형
