소소한 지식 저장소

정렬 (Sorting)데이터베이스 시스템에서 정렬이 중요한 두 가지 이유:사용자 요구: SQL의 ORDER BY 절을 통해 사용자가 결과의 정렬을 명시적으로 요구.효율적인 연산: 조인과 같은 관계 대수 연산은 입력 데이터가 정렬되어 있을 때 훨씬 효율적으로 수행 가능.정렬 기법:인덱스 활용: - 인덱스를 사용하여 논리적으로 정렬된 순서대로 데이터를 읽는 방법. - 하지만 이 경우 각 튜플에 접근할 때마다 디스크 접근이 발생하여 비용이 매우 높을 수 있음.내부 정렬 (Quicksort): 관계(데이터)가 메모리에 전부 올라갈 정도로 작을 때 사용.외부 정렬 병합 (External Sort-Merge): 관계가 메모리보다 커서 한 번에 처리할 수 없을 때 사용하는 기법1단계: 정렬된 부분 집합 (Run) 생..

주어진 데이터 묶음에서 특정 순서에 있는 값을 찾아야 할 때가 많음가장 작은 값(최소값), 가장 큰 값(최대값), 혹은 정확히 가운데에 있는 값(중간값)을 찾는 것이 대표적인 예시이를 일반화하여 "n개의 원소 중에서 i번째로 작은 원소를 찾는 문제"를 '선택 문제(Selection Problem)'- 가장 간단한 해결책은 데이터를 모두 정렬한 뒤 i번째 인덱스의 값을 가져오는 것- 힙 정렬이나 병합 정렬을 사용하면 $O(n \log n)$의 시간 복잡도로 해결할 수 있음1. 무작위 분할을 이용한 선택 (Randomized-Select)퀵 정렬(Quick Sort)과 유사한 아이디어를 사용하지만, 더 효율적으로 동작퀵 정렬이 배열을 분할한 뒤 양쪽 모두를 재귀적으로 정렬하는 반면, 우리가 찾는 원소가 있는..

비교 기반 정렬의 한계주요 비교 기반 정렬 알고리즘들과 시간복잡도알고리즘최악의 경우평균/기댓값Insertion SortΘ(n²)Θ(n²)Merge SortΘ(n lg n)Θ(n lg n)Heap SortO(n lg n)-Quick SortΘ(n²)Θ(n lg n) 비교 기반 정렬의 이론적 하한선정리 8.1: 모든 비교 기반 정렬 알고리즘은 최악의 경우 Ω(n lg n)번의 비교가 필요증명의 핵심 아이디어:결정 트리(Decision Tree)를 사용한 분석n개 원소의 가능한 순열은 n!개완전 이진 트리에서 n!개의 리프 노드를 갖기 위해서는 높이가 최소 ⌈lg(n!)⌉ ≈ n lg n따라서 최악의 경우 Ω(n lg n)번의 비교가 필요Linear Time Sorting비교 기반 정렬의 한계를 넘어서려면 비..

1. 병합 정렬 (Merge Sort)병합 정렬은 말 그대로 "나누고 합치는" 과정을 통해 전체를 정렬하는 방식아무리 복잡한 문제라도 작게 나누면 해결하기 쉽다는 '분할 정복(Divide and Conquer)' 철학에 가장 충실한 알고리즘1. 어떻게 동작하나요?분할 (Divide): - 배열의 원소가 1개가 될 때까지 계속해서 절반으로 나눔- 원소가 하나만 남은 배열은 그 자체로 '정렬된' 상태라고 할 수 있음병합 (Merge): - 이제 나누어진 작은 배열들을 다시 합침- 이때 그냥 합치는 게 아니라, 두 배열의 첫 번째 원소끼리 비교해서 더 작은 값을 먼저 가져오는 방식으로 정렬- 이 과정을 반복하면 최종적으로 완벽하게 정렬된 배열이 완성# 두 개의 정렬된 부분을 하나로 합치는 함수def merge..

정렬 알고리즘의 종류정렬 알고리즘은 크게 두 가지 방식으로 나눌 수 있음비교 기반 정렬두 데이터의 크기를 비교하며 정렬하는 방식종류: 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort), 퀵 정렬(Quick Sort) 등비교 기반 정렬은 아무리 빨라도 평균적으로 $O(n \log n)$의 시간 복잡도보다 좋을 수 없음Linear Time Sort데이터의 값을 직접 비교하지 않고, 다른 속성을 활용해 정렬합종류: 계수 정렬(Counting Sort), 기수 정렬(Radix Sort), 버킷 정렬(Bucket Sort) 등삽입 정렬 (Insertion Sort)데이터를 하나씩 확인하며, 각 데이터를 이미 정렬된 부분 배열..