got beer?

✅ 계수 정렬 (Counting Sort) ❕ 기본 개념 - 말 그대로 각 요소의 갯수를 세어서 저장해두고, 그에 따라 적절한 위치에 정렬하는 알고리즘 - 값의 범위가 너무 크면 안 되고, 각 항목의 갯수를 기록하기 위해 정수로 인덱스 되는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있다는 한계가 존재함 - 비교 정렬 알고리즘의 최소 시간복잡도가 O(n logn)인데에 비해 계수 정렬은 평균 O(n)의 시간복잡도를 가짐 - 다만 공간복잡도가 O(size)이기 때문에 메모리 낭비가 심함 ❕ 작동 방식 ✔ 구현 방법 (JS) const arr = [4, 3, 1, 2, 3]; const findMaximum = (arr) => arr.reduce((acc, val) =..

✅ 퀵 정렬 (Quick Sort) ❕ 기본 개념 - 분할 정복(divide and conquer) 방법을 통해 정렬 - 수열 안에서 기준이 되는 수인 피봇(pivot)을 임의로 하나 선택한 후, 나머지 수를 '피봇보다 작은 수'와 '피봇보다 큰 수'의 두 그룹으로 나눈다. 피봇을 기준으로 왼쪽과 오른쪽의 리스트들을 각각 정렬하면 전체 정렬이 완료됨 - 분할된 두 개의 리스트에 대해 재귀적으로 앞의 과정을 반복한다. (재귀는 리스트의 크기가 0 또는 1이 될 때까지 반복) - n의 리스트를 정렬하는데 걸리는 시간을 T(n), c는 임의의 상수라 하고, 리스트가 피봇 기준으로 두개의 비슷한 크기의 부분집합으로 나뉜다는 가정 하에 얻는 평균 시간복잡도는 O(n logn)이다. - 반면, 운이 나빠 매번 최솟..

✅ 삽입 정렬 (Insertion Sort) ❕ 기본 개념 - 자료 배열의 모든 요소를 차례대로 정렬 완료된 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 - 배열이 길어질수록 효율이 떨어지지만 구현이 간단함 - 숫자 비교 횟수는 최악의 경우에 1 + 2 + 3 + ... + (n - 1) ≈ n2 / 2 번 비교 - 따라서 시간복잡도는 O(n2), 공간복잡도는 O(1) ☜ 추가적인 메모리 필요 X ❕ 작동 방식 ✔ 구현 방법 (JS) function insertionSort(inputArr) { let n = inputArr.length; for (let i = 1; i < n; i++) { // Choosing the first element in our unsorted s..

✅ 선택 정렬 (Selection Sort) ❕ 기본 개념 - 수열 중에서 최솟값을 검색한 후 왼쪽 끝 숫자와 교체하는 작업을 반복하며 정렬 - 최솟값을 찾을 때는 선형 탐색을 사용 - 숫자 비교 횟수는 (n - 1) + (n - 2) + ... + 1 ≈ n2 / 2, 숫자 교체는 각 라운드 당 최대 1회 - 따라서 선택 정렬 시간 복잡도는 O(n2) ❕ 작동 방식 ✔ 구현 방법 (JS) function selectionSort(inputArr) { let n = inputArr.length; for (let i = 0; i < n; i++) { // Finding the smallest number in the subarray let min = i; for (let j = i + 1; j < n; j..