Mason

Quick Sort 재귀를 이용하여 배열이 1개의 아이템이 남을때까지 분할 시키며 Pivot포인트를 지정하여 정렬한다. Pivot 정렬 함수를 만들어 정렬을 실행할 아이템을 Pivot 포인트로 지정한다. 이후 배열의 아이템들을 순차적으로 Pivot과 비교하며 Pivot보다 낮은 아이템들은 배열의 왼편으로 이동시킨다. 배열의 모든 아이템들의 비교가 끝이나면 이동시킨 아이템들중 맨 오른쪽의 아이템과 Pivot의 위치를 교환한다. 이후 Pivot의 위치는 확정이 되며 Pivot을 기준으로 배열의 왼쪽 아이템들과 오른쪽 아이템들을 반복하여 진행한다. Pivot 함수 function pivot(arr, start = 0, end = arr.length - 1) { let pivotIndex = start; let..

Merge Sort 분할, 정렬, 합병 3가지의 단계로 이루어진 알고리즘으로 배열의 아이템이 0개 혹은 1개일경우 어떠한 값이 오든 배열은 정렬된 상태인것을 이용하는 방식이다. 전체 배열을 0 혹은 1개의 아이템이 남을때까지 계속해서 2분할 한후 1개의 아이템을 가진 배열 2쌍씩 비교하여 정렬후 합병하며 전체 배열이 정렬될때까지 계속해서 비교후 정렬, 합병을 반복한다. 병합 함수 Merge Sort의 마지막단계인 정렬과 합병을 수행할 함수를 먼저 만들어 준다. function merge(arr1, arr2) { let result = []; let i = 0; let j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] < arr2[j]) { ..

Bubble Sort (버블 정렬) 배열의 첫 아이템을 시작으로 다음 아이템과 비교후 정렬, 이후 두번째 아이템과 그 다음 아이템을 비교후 정렬, 이렇게 순차적으로 모든 비교를 마친후 다시 배열의 첫 아이템과 다음 아이템을 비교후 정렬하며 반복적으로 이루어 진다. 버블 정렬 예시 function bubbleSort(arr) { let swapCheck; for (let i = arr.length; i > 0; i--) { swapCheck = true; for (let j = 0; j arr[j + 1]) { let tem = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tem; swapCheck = false; } } i..

이번 포스트에서는 Linear, Binary, Naive string search algorithm에대해 알아 보겠다. Linear Search Algorithm(선형 검색 알고리즘) 배열에 있는 데이터를 검색할때 제일 쉬운 방법으로 배열의 맨 앞부터 차례대로 확인하는 검색 알고리즘이다. 배열이 정렬되지 않앗을경우 사용하기 좋으며 indexOf, includes, find, findIndex와 같은 함수들이 이에 해당한다. Linear search의 Big O notation 선형검색을 하면서 배열의 제일 처음오는 데이터를 찾게될경우 O(1)이 되겠지만 최악의 경우 배열의 제일 마지막 데이터를 찾게 될경우 O(n)이 되므로 최종 Big O notation은 O(n)이 된다. 예시) indexOf의 원리 ..

객체의 Big O 입력 = O(1) 삭제 = O(1) 탐색 = O(n) 읽기 = O(1) let person = { name: "Mason", age: 30, isKorean: true, hobbies: ["book", "music", "swimming"], }; 위와 같은 객체에서 입력, 삭제, 읽기와 같은 작업들은 해당 key를 이용하여 접근하기 때문에 O(1)의 시간복잡도를 가지고있다. 하지만 탐색의 경우 O(n)의 시간복잡도를 가지고 있으며 이는 각 아이템들마다 접근하여 검색한다음 해당하는 key를 찾기때문이다. 예를 들어 true라는 value를 가지고있는 key를 찾는다고할때 순차적으로 name과 age의 value를 탐색하고 true의 값을 가진 isKorean으로 넘어와서 검색을 마치기때문..

이번 포스트에서는 어떠한 문제에 대한 여러 해결법중 제일 효율적인 해결법을 찾기 위한 방법인 Big O notation에 대해 알아보겠다. 알고리즘에따라 많은 데이터량을 다루는 것을 잘 할수도 있고 처리시간이 좀 더 걸리더라도 데이터량에 관계없이 처리속도가 일정할수도 있다. 또한 이렇게 시간이 기준이 아닌 메모리 할당, 즉 메모리 공간을 기준으로 효율을 측정할 수도 있다. 이러한 효율을 측정하는 기준이 시간복잡도 혹은 공간복잡도이며 복잡도를 표현하는 방식은 Big-O(빅-오) : 최악의 경우를 표현 Big-Ω(빅-오메가) : 최선의 경우를 표현 Big-θ(빅-세타) : 평균의 경우를 표현 이렇게 3가지가 존재한다. 위의 3가지중 대부분 Big-O notation을 사용하는데, 이는 어떠한 알고리즘의 최악..