개발하기좋은날

퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다 1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다. 2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다. 3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다. 3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다. 풀이는 아래..

BFS (너비 우선 탐색) 정의 - 루트 노드 또는 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 동작 과정 1. 먼저 깊이가 1인 노드들(1번,2번,4번)을 먼저 방문하게 된다 2. 방문한 노드는 Queue에 넣어서 보관하게된다 3. 깊이가 1 인 경로를 전부 탐색하면 큐에서 하나씩꺼내서 다음 깊이인 깊이2 노드를 방문한다 4. 1 ~ 3 과정 반복 BFS 특징 직관적이지 않은 면이 있다. BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다. BFS는 재귀적으로 동작하지 않는다. 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다. B..

오름 차순 정렬된 정수의 배열에서 target을 찾는 문제 const binarySearch = function (arr, target) { var low = 0; var high = arr.length-1; var flag = true; var result = -1; //결과 while(flag == true) { var fv = Math.floor((low+high)/2); // 기준점 if(arr[fv]

정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴 조건 입력의 배열은 음수와 0을 포함하는 정수 입력의 배열 길이는 3이상 입력의 배열은 중첩되지 않은 1차원 배열 조합을 이용한 풀이 const largestProductOfThree = function (arr) { var com = combination(arr,3) com = com.map((v) => { return v.reduce((acc, cur) => acc * cur); }); return Math.max.apply(null, com); }; function combination(arr, selectNum) { const result = []; if (selectNum === 1) return arr.map(..

let dfs = function (node) { let values = [node.value]; node.children.forEach((n) => { values = values.concat(dfs(n)); }); return values; }; let Node = function (value) { this.value = value; this.children = []; }; Node.prototype.addChild = function (child) { this.children.push(child); return child; }; let root = new Node(1); let rootChild1 = root.addChild(new Node(2)); let rootChild2 = root.addCh..

- 버블 정렬은 요소들이 마치 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고 해서 버블 정렬이란 이름이 붙여졌다 - 아래 코드는 기존의 버블정렬의 문제점에서 더이상 정렬할 부분이 없는 경우 break문을 사용하여 시간 복잡도를 일부 줄인 코드이다. const bubbleSort = function (arr) { var length = arr.length; var i, j, temp; var flag = false; for (i = 0; i arr[j ..

- 문제 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다. - 조건 시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과 const isSubsetOf = function (base, sample) { // 값이 있으면 COUNT +1 길이만큼 있으면 RETURN TRUE // 배열 값을 정렬 // 숫자 크기 비교 38 55 이후X // 있다면 BASE 원소 제거 // 가운데 숫자 비교해서 // 처음 과 끝 사이에 포함되는 숫자인지 판별 // 가운데 처음 끝 어디서 가까운지 판별해서 찾기 시작 // 왼쪽 탐색인지 오른쪽 탐색인지 구별 base.sort((a, b) => a - b);..

피보나치 수열은 아래와 같은 특징을 가지고있다 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 재귀 형태로 호출시 아래와 같이 트리 구조로 호출이 되면 O(n^2) 형태로 표현이 된다 위 그림 처럼 사용시 불필요한 메모리를 차지한다 아래 그림처럼 불 필요 한걸 제거한다면 O(N) 형태로 아래와 같이 코드 작성이 가능하다 function _fibonacci(n, memo) { if ((memo[n] != 0) && (memo[n] != undefined)){ // 기록한거 사용 return memo[n]; } else // 기록이 없을시..