정리 노트

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