정리 노트

DML 문을 연습할 데이터 베이스는 아래의 사이트에서 스크립트를 다운로드하여 실행해 생성했습니다. MySQL Sample DatabaseThis page provides you with a MySQL sample database that helps you to practice with MySQL effectively and quickly.www.mysqltutorial.orgORDER BY 절은 SELECT 결과를 특정 열을 기준으로 정렬해 출력해 주는 역할을 합니다. ORDER BY 절에서는 기본적으로 오름차순으로 정렬하고, 내림차순으로 정렬하도록 지정할 수 있습니다.ORDER BY 절 연습을 위해 아래의 테이블을 사용하겠습니다.SELECT customerNumber, customerName, phon..

이번 포스트는 병합 정렬에 대한 두 번째 글입니다. 그러니 병합 정렬에 대해 잘 모르시는 분은 제가 저번에 적었던 글을 참고하셔도 됩니다. 2022.10.20 - [개념 정리/알고리즘] - 병합 정렬(Merge Sort) 병합 정렬 과정 다시 보기 병합 정렬을 간단하게 얘기하면 배열을 반씩 나누고 나눠진 배열들을 정렬시킨 후 정렬된 두 배열을 다시 하나의 배열로 합치는 정렬 알고리즘이었습니다. 이 과정을 Divide & Conquer의 시각에 맞춰서 보면 세 단계로 나눌 수 있었고 각각 Divide, Conquer, Combine(Merge)로 볼 수 있었습니다. 이번에는 병합 정렬 과정을 Top-down, Bottom-up 방식으로 나눠서 보겠습니다. Top-down: 하나의 커다란 문제를 여러 개의 ..

이 글은 Divide & Conquer(분할 정복 기법)을 알고 계신다는 가정 하에 작성되었습니다. 분할 정복에 대한 글은 제가 저번에 쓴 글을 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer) 병합 정렬(Merge Sort) 병합 정렬을 하는 과정을 분할 정복 기법을 사용해서 설명할 수 있습니다. 전체 배열을 반씩 나눕니다(Divide). 이 과정은 재귀적으로 진행됩니다. 반씩 나눈 배열들을 정렬합니다(Conquer). 정렬한 배열들을 다시 하나로 합칩니다(Combine). 여기서의 base case는 배열의 길이가 1인 경우입니다. 배열의 길이가 1이면 이 자체로 정렬이 되어있기 때문에 배열의 길이가 1이면 반씩 나누는 것을 그만둡니..

이 포스트는 삽입 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 저번에 적은 삽입 정렬에 관한 글이 있으니 참고하실 분은 참고하시면 됩니다. 2022.09.12 - [알고리즘] - 삽입 정렬(Insertion Sort) Shell Sort 기존의 삽입 정렬은 정렬을 위해 배열 내의 원소 간 이동이 많이 발생한다는 단점이 생깁니다. 만일 정수형 배열에서 원소 '1'이 배열의 가장 끝에 있다고 해봅시다. 그럼 원소 '1'을 배열의 거의 앞에 놓기 위해 거의 모든 원소들이 한 칸씩 옆으로 이동하는 연산을 수행해야 합니다. Shell 정렬은 이러한 문제점을 개선하기 위해 생겼습니다. Shell 정렬에서는 gap만큼 떨어진 원소들끼리의 삽입 정렬을 진행해서 적은 데이터의 이동으로 작은 값을 앞으로 당겨올 수..

삽입 정렬 정렬을 하다 보면 배열 안의 데이터들을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 삽입 정렬은 정렬되지 않은 데이터들 중 가장 앞의 데이터를 정렬된 부분에서의 자기 위치를 찾아 정렬하는 방법입니다. 정렬 과정 길이가 6인 정수형 배열({3, 1, 4, 4, 6, 5})을 정렬해봅시다. 먼저 3을 정렬하려면 정렬된 부분과의 대소 비교를 통해 자기 위치를 찾아야 합니다. 하지만 지금은 정렬 시작 단계이기 때문에 정렬된 부분이 없습니다. 따라서 실질적인 삽입 정렬의 시작은 두 번째 원소인 '1'에서부터 시작하고 3은 정렬된 부분으로 포함시킵니다. 정렬되지 않은 원소들 중 가장 앞인 '1' 원소의 위치를 찾기 위해 정렬된 부분의 '3'과 비교합니다. 1이 3보다 작으므로 3과 1의 위치..

선택 정렬(Selection Sort) 선택 정렬은 원소들 중 가장 작은(큰) 값을 정렬되지 않은 부분의 가장 왼쪽(오른쪽)과 swap 하는 정렬 알고리즘입니다. 과정 길이가 6인 정렬되지 않은 정수형 배열({1, 2, 4, 6, 3, 5})를 정렬한다고 해봅시다. 1과 2는 이미 작은 순으로 정렬되어있으므로 여기에 대해서는 swap이 일어나지 않습니다. 다음에는 정렬되지 않은 부분에서 가장 작은 값은 3입니다. 3을 제 위치에 놓기 위해 4와 자리를 swap 합니다. 나머지 4, 5 원소도 위와 같은 단계를 거쳐 배열 정렬을 마무리합니다. 선택 정렬 코드(C++) #include using namespace std; void selectionSort(int[], int); int main() { int..

이번 포스트도 버블 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 버블 정렬을 모르시는 분들은 제가 전에 적었던 글을 참고하시기 바랍니다. 2022.09.05 - [알고리즘] - 버블 정렬(Bubble sort) Comb Sort 2022.09.06 - [알고리즘] - 칵테일 셰이커 정렬(Cocktail Shaker Sort) 에서 적었듯이 기존 버블 정렬에는 아쉬운 점이 있었습니다. 크기가 작은 데이터가 배열의 끝에 위치한 경우 제 위치로 찾아가기까지 오래 걸렸습니다. Comb Sort는 이 문제점을 개선한 정렬 알고리즘입니다. Gap 기존 버블 정렬에서는 등장하지 않았던 'gap'이 등장합니다. gap은 현재 데이터와 swap 할 데이터 간의 거리를 의미합니다. 즉 버블 정렬에서는 gap이 1이..

본 글은 버블 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 버블 정렬을 모르시는 분들은 제가 전에 썼던 글을 보고 오시면 더 편하게 이해하실 수 있습니다. 2022.09.05 - [알고리즘] - 버블 정렬(Bubble sort) 버블 정렬할 때 생기는 문제점 버블 정렬을 할 때 길이가 5인 정수형 배열({5, 4, 3, 2, 1})을 정렬한다고 생각합시다. 5는 1번의 pass로 제 위치로 갈 수 있지만 1은 마지막 pass까지 진행해야 제 위치로 갑니다. 이렇듯 정수형 배열을 정렬할 때 값들이 임의로 섞여있는 경우 큰 값들은 적은 pass를 통해 정렬되지만 작은 값들은 거의 마지막 pass까지 진행해야 합니다. 여기서 크기가 작은 값들을 빠르게 제 위치로 이동시킬 수 있는 칵테일 셰이커 정렬(C..