알고리즘

문제분석주어진 함수의 결과를 캐시에 저장하고, 같은 입력에 대해서는 다시 계산하지 않고 저장된 결과를 반환하도록 하는 것이다.알고리즘 설계캐시 저장소 만들기함수 호출횟수 추적함수의 입력을 문자열로 변환fn이 호출될대마다 캐시에서 결과를 찾아 있으면 반환없으면 실제 함수를 호출하고 결과를 캐시에 저장한다. 구현/** * @param {Function} fn * @return {Function} */function memoize(fn) { const cache = new Map(); return function(...args) { const key = args.toString(); if (cache.has(key)) { return cache.get(k..

javascript 로 구현해보기class Node { constructor(element) { this.element = element; this.next = null; }}class LinkedList { constructor() { this.head = new Node("head"); } insert(newElement, item) { let newNode = new Node(newElement); //새로운 노드 생성 let current = this.find(item); // 삽입할 위치의 노드 찾기 newNode.next = current.next; // 찾은 노드가 가리키는 노드를 새로은 노드가 가리키기 current.next = newNode;..

배열 순차검색 일반적으로 배열은 동일한 크기를 갖고 빈틈없이 연속적으로 이어져있다. 인덱스를 통해 단한번의 연산으로 임의의 요소에 접근할수있다. 하지만 정렬되지않는 배열에서 특정한 값을 탐색하는 경우, 모든 배열요소를 처음부터 값을 발견할때까지 차례대로 탐색해야한다. // 선형 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여// 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수function linearSearch(array, target) { const length = array.length; for (let i = 0; i   맨앞의 7의 숫자를 검색하는것보다. 맨뒤에있는 30을 검색한다면 7.076ms -> 7.503ms ..

피보나치 수열의 유래?  피보나치 수열은 규칙을 발견한 수학자 레오나르도 피보나치의 이름을 따 부르게 되었다. 레오나르도 피보나치는 이탈리아 수학자로 이집트, 그리스, 시칠리아 등의 나라를 여행하며 아라비아에서 발전된 수학을 두루 섭렵하였다고한다. 그 많은 업적 중 피보나치수열은 12세기말 이탈리아에서 처음 제안한 것으로 "한 쌍의 토끼가 계속 새끼를 낳으면 몇 마리로 불어 날까?를 연구하다 새로운 수의 체계를 발견하였다고 한다. 한쌍의 토끼는 매일 암수 한쌍의 새끼를 낳으며 새로 태어난 토끼도 태어난지 두달 후 부턴 매달 한쌍씩 암수 새끼를 낳는다고 한다. 그러면 농장주는 1년이 지난후 모두 몇쌍의 토끼를 갖게 될까?    그 결과 피보나치는 매달 관찰되는 토끼의 양이 특정한 규칙을 따르고 있음을 발견..

해쉬란? 해쉬는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말한다. 다른 말로는 해시 값이라고한다. 사용하는경우 배열의 인덱스위치, 위치, 데이터 값을 저장하거나 검색할때 활용된다. 특징 키(KEY)에 데이터(VALUE)를 매핑할 수 있는 데이터 구조 해쉬 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산 장단점 장점 데이터 저장/ 읽기 속도가 빠름 (검색속도가 빠름) 해시는 키에 대한 데이터가 있는지 확인이 쉬움 단점 일반적으로 저장곤간이 많이 필요 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요 코드 class hashTable{ constructor(size){ this.storage = []; if(size){ this.s..

그리디 알고리즘이란? 최적의 값을 구해야하는 상황에서 사용되는 방법으로 ' 매선택에서 지금 이순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자' 가 모토이다. 비유하자면 마시멜로 실험을 생각하면된다 -> 그리디 알고리즘을 사용한다는것은 당장 눈앞에있는 마시멜로를 먹는것이다. 하지만 이방법을 사용하는것은 기다렸다가 2개를 먹는다라는 최적해를 보장해주지 못한다 사용하는이유 항상 최적의 선택을하기때문에 앞서봤던 깊이우선탐색(dp) 보다 빠른 속도를 낸다 특징 최적부분 구조이다. -> 한번의 선택이 다음선택에는 전혀 무관한 값이며 매순간의 최적해가 문제에대한 최적해야여한다는의미이다. 원리 위의 그림을 보면서 아래 설명의 봐보자. 1. 시작 정점을 7로 설정 (최대값을 구할때) 2. 3과 12중에 하나를 골..