정리 노트

이 글은 Divide & Conquer에 대해 기본적인 내용을 알고 계신다는 가정 하에 작성되었습니다. 따라서 분할 정복 기법에 대해 잘 모르시는 분들은 제가 저번에 썼던 글을 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer) 퀵 정렬 이름 그대로 빠르게 정렬하는 알고리즘입니다. 퀵 정렬도 분할 정복 기법 방식으로 설명할 수 있습니다. Divide: 배열의 원소들 중 임의의 원소 하나를 기준(pivot)으로 정하고 기준보다 작은 원소들의 그룹과 큰 원소들의 그룹으로 나눕니다. Conquer: 기준점을 중심으로 나누어진 두 그룹을 recursive 하게 quick sort를 수행합니다. 이 설명에서는 'combine' 과정이 빠져있습니다...

이번 포스트는 병합 정렬에 대한 두 번째 글입니다. 그러니 병합 정렬에 대해 잘 모르시는 분은 제가 저번에 적었던 글을 참고하셔도 됩니다. 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이면 반씩 나누는 것을 그만둡니..

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 해결 과정 분할(Divide): 문제를 2개 이상의 같은 형식의 작은 문제들로 나눕니다. 정복(Conquer): 나눠진 작은 문제들은 재귀적으로 해결합니다. 나눠서 문제를 해결할 필요가 없을 때까지 계속 분할해 나갑니다. 통합(Combine): 풀어낸 작은 문제들의 해답들을 합쳐서 원래 문제의 해답으로 만듭니다. 위에 적은 과정이 주로 분할 정복 기법을 사용해 문제를 풀어나가는 과정입니다. 정복 과정에서 문제들을 재귀적으로 해결해 나가기 때문에 재귀를 이용해서 구현하게 됩니다. 따라서 재귀에 대해 어느 정도 아셔야 합니다. ..

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 수학에서 얘기하는 재귀 어떤 함수를 정의하는데 자기 자신의 함수를 이용하는 것을 재귀라고 합니다. 재귀를 흔히 점화식의 형태로 나타낼 수 있습니다. 예를 들어 자연수 n에 대한 함수 f(n) = n! 가 있다고 합시다. 이를 아래와 같이 정의할 수 있습니다. 이 정의를 보면 n! 를 정의하는데 다시 (n - 1)!로 정의합니다. n > 0일 때 식을 풀어써봅시다. n * (n - 1)! = n * (n - 1) * (n - 2)! = n * (n - 1) * (n - 2) * (n - 3)! =... = n * (n - 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..