전체 글
제코베 JS 100제 / 52 / quick sort
function quickSort(arr) { if (arr.length parseInt(n, 10)); console.log(quickSort(array)); 위의 코드에선 pivot을 배열의 가장 첫번째 값으로 잡았지만, 중간값으로 잡는게 좋다고 한다. quick sort는 정렬이 불필요한 배열이 들어와도 수행하게 되는데, 이 경우 최악의 경우로 O(n^2)의 시간 복잡도를 가지게 된다. 어떤 배열이 들어올지 미지수인 상태에서 quick sort를 구현하게 된다면, 그나마 최소나 최대값이 아닌 확률이 가장적은 중간값으로 pivot을 잡는것이다.
제코베 JS 100제 / 51 / merge sort를 만들어보자
병합정렬은(merge sort)은 대표적인 정렬 알고리즘 중 하나로 다음과 같이 동작한다. 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. function mergeSort(arr) { if (arr.length parseInt(n, 10)); console.log(mergeSort(array)); 2022.08.18 - [ALGORITHM/정렬] - Algorithm / 정렬 / Merge Sort (합병 정렬) (따로 포스팅했던 Merge Sort의 동작 ..
Programmers / Level 3 / 자물쇠와 열쇠 / JS
문제 설명 고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 ..
Programmers / Level 2 / 124 나라의 숫자 / JS
문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 제한사항 n은 500,000,000이하의 자연수 입니다. 입출력 예 n result 1 1 2 2 3 4 4 11 function solution(..
Algorithm / 정렬 / Merge Sort (합병 정렬)
합병 정렬 function merge(left_arr, right_arr) { let result = []; let [i, j] = [0, 0]; while (i < left_arr.length && j < right_arr.length) { if (left_arr[i] < right_arr[j]) { result.push(left_arr[i]); i++; } else { result.push(right_arr[j]); j++; } } while (i < left_arr.length) { result.push(left_arr[i]); i++; } while (j < right_arr.length) { result.push(right_arr[j]); j++; } return result; } functio..
Algorithm / 정렬 / Insertion Sort (삽입 정렬)
삽입 정렬 function insertion_sort(arr) { console.log(`Before insertion sorting: ${[...arr]}`); let cnt = 0; for (var i = 1; i = 0 && arr[j] > cur; j--) { if (cur < arr[j]) arr[j + 1] = arr[j]; cnt++; } arr[j + 1] = cur; } console.log(`After insertion sorting: ${[...arr]}`); console.log(`Sorting count = ${cnt}`); } let arr = [3, 6, 13, 4..