섹션 17: 기수 정렬버블, 선택, 삽입, 합병, 퀵 정렬은 비교 정렬에 속한다. 반면 기수 정렬은 정렬할 숫자를 비교하지 않고 bucket이라는 10개의 배열(0~9)에 담았다가 병합하는 방식으로 정렬한다. 이렇게 bucket에 담았다가 병합하는 과정은 정렬할 숫자의 최대 자릿수만큼 일어난다. // 자릿수에 해당하는 숫자 반환function getDigit(num, i) { return Math.floor(Math.abs(num) / Math.pow(10, i) % 10);}// 숫자의 자리수 세기function digitCount(num) { if (num === 0) return 1; // log 계산은 지수와 밑이 같으면 1이다. // 지수가 10이기 때문에 두자리 수인 10..

섹션 16: 퀵 정렬이 코드는 배열에서 가장 왼쪽의 값을 피봇으로 삼는 방식으로 작성되어 있다. 피봇 값 보다 작은 값은 피봇 값 왼쪽에 위치하도록 하는 정렬 방식으로 재귀 함수를 이용해 이 과정을 반복하여 정렬한다. function pivot(arr, start = 0, end = arr.length + 1) { function swap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]] } var pivot = arr[start] var swapIdx = start for (var i = start + 1; i arr[i]) { swapIdx++ swap(arr, swapIdx, i) ..

섹션 15: 합병 정렬1948 폰 노이만이 최초로 작성하였다. 분할, 정렬, 합병 조합으로 정렬한다. 아래는 재귀함수를 이용한 코드이다.function merge(arr1, arr2) { const results = []; let i = 0; let j = 0; while (i arr1[i]) { results.push(arr1[i]); i++; } else { results.push(arr2[j]); j++; } } while (i  Big O버블, 삽입, 선택 정렬 대비-평균적으로-훨씬 유리한 시간 복잡도를 가지지만 공간 복잡도는 불리하다. AlgorithmTime..

섹션 11: 버블 정렬버블 정렬은-오름차순인 경우-순회하면서 가장 큰 수를 가장 뒤로 보내는 정렬 방식이다.function bubbleSort(arr) { for (let i = arr.length; i > 0; i--) { for (let j = 0; j arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr;}console.log(bubbleSort([9, 3, 5, 2, 1])); 스왑 여부를 체크하여 스왑이 일어나지 않을 경우에는 반복을 중단하여 최적화하였다.일반적으로 O(n^2), 가능한 최고의 경우 O(n)이다.function bubbleSort(arr) { let noSw..

섹션 5: 문제 해결 패턴📌 빈도수 세기 패턴 (Frequency Counters)[1, 2, 3], [1, 4, 9] 왼쪽 배열 요소의 제곱이 오른쪽 배열 요소에 딱 맞게 있으면 true, 그렇지 않으면 false를 반환하는 문제indexOf 메서드가 for문 안에 있는 방식의 풀이 코드는 O(n^2) 시간 복잡도를 가진다. indexOf 메서드가 O(n)의 시간 복잡도를 가지고 있어서 중첩 for문과 같은 조건이 되어버리기 때문이다. 따라서 for문 안에서 indexOf  메서드를 사용하는 코드 대신에 for문을 여러 번 사용하더라도 반복문이 중첩되지 않도록 하는 것이 성능에 유리하다. 또한 배열의 경우 객체(배열 요소는 키, 동일 배열 요소의 개수는 값)로 만들면 O(1)의 시간 복잡도로 필..

섹션 4: 문제 해결 접근법 📌 알고리즘 특정 작업을 달성하기 위한 과정이나 일련의 단계 📌 문제 해결법 1단계 문제의 이해 작업을 수행하면서 어떤 해결책을 마련할지, 애플리케이션이 어떻게 구동되도록 할지, 각 상황에서 어떤 식으로 작동되도록 할지에 대해 확실히 이해한다. 면접관에게 질문을 던져서 문제를 명확히 함으로써 확실히 이해할 수도 있다. 문제 이해는 구체적인 예시를 살펴보는 것과도 관련된다. 2단계 구체적 예시 이 두 가지 단계(문제의 이해, 구체적 예시)는 문제를 이해하고, 입력값과 출력값을 이해하고 경계 조건을 이해하는 것에 관한 것이다. 에러를 어떻게 처리할지, 그리고 사용자가 잘못된 값을 입력하면 어떻게 되는지와 같은 질문들은 처음부터 모든 것이 어떻게 작동해야 하는지를 이해하는 것과 관..

섹션 3: 배열과 오브젝트의 성능 평가 📌 객체의 빅오 1. 객체 키, 값의 삽입, 삭제, 접근의 경우 Insertion, Removal, Access → O(1) 2. 객체의 키로 접근하지 않고 값으로 탐색하는 경우 Searching → O(n) 3. 객체 메서드의 빅오 O(n) Object.keys Object.values Object.entries O(1) Object.hasOwnProperty let instructor = { firstName: "김일남", isInstructor: true, favoriteNumbers: [1,2,3,4] } instructor.hasOwnProperty("firstName"); // true 📌 배열의 빅오 1. 배열 앞이나 중간 인덱스에 요소 삽입, 삭제 배..

섹션 2: 빅오 표기법(Big O Notation) 📌 Big O Big O는 코드의 성능을 숫자로 표현하는 것이다. What does better mean? Faster? Less memory-intensive? More readable? 📌 시간 복잡도(Time Complexity) 1~n까지의 합을 구할 때 for문을 이용하는 방법과, 수학 공식 n*(n+1)/2를 이용하는 방법을 비교해 보자! // 코드 수행 시간 측정 var time1 = performance.now() addUpTo(1000000000) var time2 = performance.now() console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`) 위 코드와 같은 방식으로..