반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 22: 고급 정렬 알고리즘 (TimSort, IntroSort) 고급 정렬 알고리즘정렬 알고리즘은 데이터 처리와 분석에서 매우 중요한 역할을 합니다. 오늘은 두 가지 고급 정렬 알고리즘인 TimSort와 IntroSort에 대해 학습하겠습니다. 이 두 알고리즘은 효율성과 안정성 측면에서 매우 강력하며, 실세계에서 널리 사용됩니다.TimSortTimSort는 삽입 정렬과 병합 정렬을 혼합한 하이브리드 정렬 알고리즘입니다. 이 알고리즘은 실제 데이터가 부분적으로 정렬되어 있는 경우 매우 효율적입니다. Python의 sort() 함수와 Java의 Arrays.sort()에서 사용되는 기본 정렬 알고리즘이기도 합니다.TimSort의 주요 단계Runs 분할: 주어진 배열을 일정 크기(기본적으로 32 또는 64)로 분할하여 각각을 정렬합니다.Runs 병합: 병합 정렬을 사용하여.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 20: 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort)힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 최대 힙 또는 최소 힙을 사용하여 배열을 정렬합니다. 힙 정렬은 평균 및 최악의 경우 시간 복잡도가 (O(n \log n))입니다.힙 정렬의 주요 단계:힙 구성 (Heapify): 배열을 이진 힙으로 변환합니다.정렬 (Sort): 힙의 루트 요소를 제거하고, 힙을 재구성하여 정렬된 배열을 만듭니다.힙 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n \log n))최선의 경우: (O(n \log n))힙 정렬 구현힙 구성 함수힙 속성을 유지하면서 배열을 이진 힙으로 변환합니다.#include #include // 힙 구성 함수void heapify(std::vector& arr, int n, int.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 19: 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort)퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 피벗(Pivot)을 기준으로 두 개의 하위 배열로 나눈 다음, 각각을 정렬합니다. 퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘으로 간주됩니다.퀵 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n^2))최선의 경우: (O(n \log n))퀵 정렬의 공간 복잡도:(O(\log n)) (재귀 호출 스택 공간)퀵 정렬 구현퀵 정렬의 주요 단계:분할 (Partition): 피벗을 기준으로 배열을 두 부분으로 나눕니다.정복 (Conquer): 하위 배열을 재귀적으로 정렬합니다.결합 (Combine): 분할된 하위 배열이 정렬된 상태이므로 추가.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 16: 버블 정렬과 선택 정렬 버블 정렬 (Bubble Sort)버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 자리를 바꾸면서 배열을 정렬합니다. 배열의 끝까지 이 과정을 반복하면 가장 큰 값이 맨 끝에 위치하게 됩니다. 이 과정을 여러 번 반복하여 배열이 정렬될 때까지 진행합니다.버블 정렬의 시간 복잡도:최선의 경우: (O(n))평균의 경우: (O(n^2))최악의 경우: (O(n^2))버블 정렬 구현#include #include // 버블 정렬 함수void bubbleSort(std::vector& arr) { int n = arr.size(); for (int i = 0; i arr[j + 1]) { std::swap(arr[j], arr[j +.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 17: 삽입 정렬과 쉘 정렬 삽입 정렬 (Insertion Sort)삽입 정렬은 배열의 요소를 하나씩 정렬된 부분에 삽입하는 방식으로 동작합니다. 각 요소를 적절한 위치에 삽입하기 위해 이미 정렬된 부분을 오른쪽으로 이동시킵니다.삽입 정렬의 시간 복잡도:최선의 경우: (O(n))평균의 경우: (O(n^2))최악의 경우: (O(n^2))삽입 정렬 구현#include #include // 삽입 정렬 함수void insertionSort(std::vector& arr) { int n = arr.size(); for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 정렬된 부분에서 키보다 큰 요소 이동 --j; } .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 15: 정렬 알고리즘 개요 정렬 알고리즘 (Sorting Algorithms)정렬 알고리즘은 주어진 데이터를 특정 순서대로 정렬하는 알고리즘입니다. 정렬은 컴퓨터 과학에서 매우 중요한 개념으로, 데이터의 효율적인 검색 및 정렬된 데이터를 필요로 하는 다양한 알고리즘의 기반이 됩니다.정렬 알고리즘의 종류:버블 정렬 (Bubble Sort)선택 정렬 (Selection Sort)삽입 정렬 (Insertion Sort)합병 정렬 (Merge Sort)퀵 정렬 (Quick Sort)힙 정렬 (Heap Sort)기수 정렬 (Radix Sort)계수 정렬 (Counting Sort)정렬 알고리즘 비교비교 기준:시간 복잡도 (Time Complexity): 알고리즘이 실행되는 데 걸리는 시간의 척도입니다.공간 복잡도 (Space Complex.. 2024. 8. 1. [알고리즘] 3. 정렬 Index 1. 정렬 2. 버블 정렬 3. 삽입 정렬 4. 선택 정렬 5. 퀵 정렬 6. 병합 정렬 7. 계수 정렬 8. 추천 문제 9. 참고자료1. 정렬정렬(Sort)- 데이터를 특정한 기준에 따라 순서대로 나열하는 것 2. 버블 정렬버블 정렬(Bubble Sort) def bubble_sort(arr: list): for i in range(len(arr)): for j in range(len(arr)-1): if (arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr3. 삽입 정렬삽입 정렬(Insertion Sort)- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입- .. 2024. 7. 19. [C++로 배우는 알고리즘과 자료구조] 목차 C++로 배우는 알고리즘과 자료구조 시리즈Day 1: 알고리즘과 자료구조 소개Day 2: 배열과 문자열Day 3: 연결 리스트 (단일, 이중, 원형)Day 4: 스택과 큐Day 5: 해시 테이블Day 6: 트리의 기본 개념Day 7: 이진 탐색 트리 (BST)Day 8: 균형 이진 탐색 트리 (AVL 트리)Day 9: 힙과 우선순위 큐Day 10: 트라이 (Trie)Day 11: 그래프의 기본 개념Day 12: 그래프 표현 방법 (인접 리스트, 인접 행렬)Day 13: 이진 힙과 힙 정렬Day 14: 해시 함수와 충돌 해결 기법Day 15: 정렬 알고리즘 개요Day 16: 버블 정렬과 선택 정렬Day 17: 삽입 정렬과 쉘 정렬Day 18: 합병 정렬Day 19: 퀵 정렬Day 20: 힙 정렬Day 21.. 2024. 6. 20. 이전 1 다음 반응형
