해시 테이블은 고정된 크기의 자료 구조로 처음에 크기가 정해진다. 해시 테이블을 사용하면 자료를 쉽고 빠르게 저장할 수 있고 키-값 쌍을 기반으로 자료를 얻을 수 있다.자바스크립트에서 객체는 해시 테이블과 같은 방식으로 키(속성)와 해당 키의 연관된 값을 정의하는 방식으로 동작한다. 해시 테이블에는 put()과 get()이라는 함수가 있다. 시간복잡도 O(1) ex) localStorage 해싱 기법 좋은 해시 함수가 되기 위한 요구 사항 1. 결정성 : 동일한 키는 동일한 해시 값을 생성해야 한다. 2. 효율성 : 시간 복잡도가 O(1)이어야 한다. 3. 균일한 분배 : 배열 전체를 최대한 활용해야 한다. 소수 해싱 : 소수를 사용한 모듈러 나눗셈이 균일한 방식으로 배열 인덱스를 생성한다. => 충돌이..
검색 선형 검색 : 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작 function linearSearch(array, n) { for (var i = 0; i < array.length; i++) { if (array[i] == n) { return true; } } return false; } console.log(linearSearch([1,2,3,4], 4)); console.log(linearSearch([1,2,3,4], 5)); 시간복잡도: O(n) 이진 검색 : 중간 값을 확인해 원하는 값보다 해당 중간 값이 큰지 작은지 확인한다. 원하는 값이 중간 값보다 작은 경우 이진 검색 알고리즘은 중간 값보다 작은 쪽을 검색하고 원하는 값이 중간 값보다 중간 값보다 큰 경우 중간 값보다 큰..
집합은 정렬되지 않은 유일한 항목들의 그룹이다. var exampleSet = new Set(); exampleSet.add(1); // exampleSet: Set(1) {1} exampleSet.delete(1); // true exampleSet.has(1); // false 기타 유틸리티 함수 function intersectSets (setA, setB) { var intersection = new Set(); for (var elem of setB) { if (setA.has(elem)) { intersection.add(elem); } } return intersection; } var setA = new Set([1, 2, 3, 4]), setB = new Set([2, 3]); inter..
재귀 호출은 운영체제의 메모리 스택에 저장돼야 하는데, 재귀함수는 이러한 재귀 호출로 인해 발생하는 추가적인 공간 복잡도 비용을 지닌다. 피보나치수열 기본 function getNthFibo(n) { if (n = endPos) { return true; } if (word.charAt(beginPos) != word.charAt(endPos)) { return false; } else { return isPalindromeHelper(word, beginPos + 1, endPos - 1); } } isPalindromeRecursive('hi'); // false isPalindromeRecursive('iii'); // true isPalindromeRecursive('ii'); // true is..
DOM 메모리 누수 DOM 항목을 가리키는 변수가 이벤트 콜백 외부에 선언된 경우 해당 DOM 항목을 제거하더라도 해당 항목은 여전히 메모리에 남게 된다. // DOM leak: var one = document.getElementById("one"); var two = document.getElementById("two"); one.addEventListener('click', function(){ two.remove(); console.log(two); // will print the html even after deletion }); // fix for above var one = document.getElementById("one"); one.addEventListener('click', func..
배열에서 2개더한게 weight인 배열 index 찾기(hash table 사용) function findSumBetter(arr, weight) { var hashtable = {}; for (var i = 0, arrLength = arr.length; i < arrLength; i++) { var currentElement = arr[i], difference = weight - currentElement; // check the right one already exists if (hashtable[currentElement] != undefined) { return [i, hashtable[currentElement]]; } else { // store index hashtable[differen..