Yepchani's place

들어가며지난 시간에는 기본적인 정렬 알고리즘에 대해 알아봤는데요. 이번 시간에는 그보다 효율적인 정렬 알고리즘에 대해 알아보겠습니다. 병합 정렬(Merge sort)분할 정복 알고리즘의 대표적인 예로, 리스트를 반으로 나누어 정렬한 뒤 다시 병합하는 방식으로 동작합니다. 병합 정렬의 동작 과정은 다음과 같습니다.원소 개수가 1 또는 0이 될 때까지 리스트를 절반으로 나눕니다.각 부분 리스트를 정렬합니다.정렬된 두 부분 리스트를 병합합니다.      시간복잡도O(n log n) 공간복잡도O(n) 특징분할 정복 알고리즘안정 정렬추가적인 메모리 공간 필요병렬 처리에 적합대규모 데이터 처리에 효과적 힙 정렬(Heapsort)힙 자료구조를 활용하여 정렬을 수행하는 알고리즘입니다. 동작 과정은 다음과 같습니다.주어..

들어가며이번 시간에는 기본 정렬 알고리즘에는 어떤 것들이 있는지 알아보겠습니다.버블 정렬(Bubble sort)리스트의 첫 원소부터 시작해 인접한 두 원소를 비교하여 정렬하는 가장 단순한 알고리즘입니다.동작 과정은 다음과 같습니다.리스트의 첫 번째 원소부터 마지막 원소까지 인접한 두 원소를 비교합니다.앞의 원소가 뒤의 원소보다 크다면 두 원소의 위치를 서로 바꿉니다.이 과정을 리스트의 마지막 원소까지 반복합니다.이 과정을 리스트가 정렬될 때까지 반복합니다.  시간 복잡도O(n²)최선의 경우 O(n). 리스트가 이미 정렬되어 있는 경우 정렬을 한 번만 수행하면 됩니다. 공간 복잡도O(1) 특징안정 정렬제자리 정렬리스트가 이미 정렬되어 있는 경우 효율적거의 모든 상황에서 최악의 성능 정렬이 이루어지는 모습이..

들어가며 이번 시간에는 알고리즘 중 하나인 '그리디 알고리즘'에 대해 알아보려고 합니다. 소개 그리디(Greedy) 알고리즘, 또는 탐욕법 알고리즘은 매 순간에서 가장 최적의 선택을 통해 문제를 해결하는 방식입니다. 그리디라는 단어는 '탐욕적인'이라는 의미를 가지고 있죠. 이 알고리즘의 핵심은 각 단계에서 '현재 가장 좋은 선택'을 하는 것입니다. 주요 특징 그리디 알고리즘이 가지는 주요 특징은 다음과 같습니다. 탐욕적 선택 속성 알고리즘이 진행되는 동안, 각 단계에서 최적의 선택을 합니다. 이 선택은 이후의 선택 전략에 영향을 주지 않습니다. 최적 부분 구조 문제 전체에 대한 최적해(global optimum)가 부분 문제에 대해서도 최적해(local optimum)를 포함하고 있습니다. 접근 방법 그..

정렬을 할 때 Array.prototype.sort()를 사용하곤 하는데요. 시간복잡도가 평균 O(n log n)이라는 내용을 보고 문득 이런 궁금증이 생겼습니다. 'sort 메서드는 과연 어떤 정렬 알고리즘을 사용할까?' 지금부터 같이 알아보시죠! 먼저 다음 내용을 알아두셔야 합니다. 자바스크립트 엔진에 따라 sort 메서드 내부적으로 사용되는 정렬 알고리즘이 다르다. 각 엔진 별로 어떤 정렬 알고리즘을 사용하는지 간단하게 알아보겠습니다. 1. V8 (Chrome, Edge, Node.js) 버전 7.0 이전에는 Insertion Sort와 Quick Sort를 사용했습니다. The basis is a Quicksort with an Insertion Sort fall-back for shorter a..