개발/알고리즘
[알고리즘] 기수정렬
1. 기수정렬 방법 기존 정렬과는 다르게 숫자의 크기를 비교하지 않는다. 하지만 정렬할때 사용할 실제 데이터는 숫자여야 한다. 비교하는 대신 숫자크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용한다. 이 말의 의미는 자릿수가 더 큰수가 더 크다는 것이다. 2. 헬퍼 메소드 자릿수 알아내기, 수와 위치를 가져온 다음 그 위치의 숫자를 반환한다. function getDigit(num, i) { return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10; } function digitCount(num) { if (num === 0) return 1; return Math.floor(Math.log10(Math.abs(num))) + 1; } function mos..
[알고리즘] 퀵정렬
1. 퀵정렬 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을때까지 분할하여 개별적으로 정렬되는 방식 피벗포인트라 부르는 단일 요소를 선택하여 수행한다. 그러니 어떤 배열에서 어떤 요소를 선택하든 사실상 문제가 되지 않는다. 2. 퀵정렬 순서 선택한 숫자보다 작은숫자를 왼쪽으로 옮긴다 선택한 숫자보다 큰숫자를 오른쪽으로 옮긴다. 이 때 선택한 숫자는 올바른 위치이다. 이 과정을 왼쪽과 오른쪽에 반복한다. 예시) [5,2,1,8,4,7,6,3] 5선택 3,2,1,4 5 7,6,8 왼쪽 다루기 1,2,3,4 5 7,6,8 오른쪽 다루기 1,2,3,4,5,6,7,8 3. 구현 (1) pivot 함수 function pivot(arr, start = 0, end = arr.length - 1) { cons..
[알고리즘] 합병정렬
1. 합병정렬 기존 버블, 선택, 삽입정렬은 O(N^2)의 시간복잡도를 가진다. 합병정렬을 통해 o(NlogN)으로 향상시킬 수 있다. 합병 정렬은 분해와 합병 2가지 순서로 나눌수 있다. 예시 ) [8,3,5,4,7,6,1,2] 반으로 분할하여 시작 [8,3,5,4] [7,6,1,2] 다시 나눔 [8,3] [5,4] [7,6] [1,2] 다시 나눔 [8] [3] [5] [4] [7] [6] [1] [2] 정렬하면서 합친다. [3,8] [4,5] [6,7] [1,2] [3,4,5,8] [1,2,6,7] [1,2,3,4,5,6,7,8] 2. 합병정렬 순서 (1) 빈배열 만들기, 입력 두개를 취하는 함수를 정의하여 마지막에 반환할 빈 뱅열 만들기 (2) i와 j가 각각 배열끝에 도달하지 않았다면 첫번째 배열..
[알고리즘] 버블정렬, 선택정렬, 삽입정렬
1. 버블정렬 (1) 개념 버블정렬의 개념은 배열을 가장 작은 숫자에서 가장 큰 숫자순으로 오름차순으로 정렬을 한다면 더 큰 숫자가 한번에 하나씩 뒤로 이동한다. (2) 예시 [5,1,2,3,4] [1,5,2,3,4] [1,2,5,3,4] [1,2,3,5,4] [1,2,3,4,5] (3) 코드 function bubbleSort(arr) { const swap = (arr, idx1, idx2) => { [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]; }; for (let i = arr.length; i > 0; i--) { for (let j = 0; j arr[j + 1]) { swap(arr, j, j + 1..
[알고리즘] 선형검색, 이진검색
1. 선형검색 선형검색은 처음부터 끝까지 한번에 하나씩 검색하는 것이다. indexOf, includes, find, findIndex 등이 있다. 시간복잡도 : O(n) (문제) arr, num 2개의 매개변수가 주어지는데 arr안에 num가 있다면 인덱스 추출 num가 없다면 -1 return console.log(linearSearch([10, 15, 20, 25, 30], 15)); // 1 console.log(linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4)); // 5 console.log(linearSearch([100], 100)); // 0 console.log(linearSearch([1, 2, 3, 4, 5], 6)); // -1 console.l..
[알고리즘] 재귀함수 문제 모음
1. 문자열 거꾸로 만들기 (예시) console.log(reverse("awesome")); // 'emosewa' console.log(reverse("rithmschool")); // 'loohcsmhtir' (코드) function reverse(str) { if (str.length === 0) return ""; return reverse(str.slice(1)) + str[0]; } 2. 문자가 대칭인지 확인하기 (예시) console.log(isPalindrome("awesome")); // false console.log(isPalindrome("foobar")); // false console.log(isPalindrome("tacocat")); // true console.log(is..