개발하기좋은날

퀵 정렬은 합병정렬과 비슷하게 분할정복(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..

문제 내용 : 현재의 비밀번호를 새 비밀번호로 변경하는데 필요한 최소 동작의 수를 리턴하는것 조건 : - 1000이상의 숫자 - 한 번에 한 개의 숫자만 변경 가능 - 4자리의 소수인 비밀번호로만 변경 가능 풀이 과정 : 처음에는 BFS 알고리즘 적용하여 풀생각을 못하여 무작정 풀었지만 몇개의 테스트 케이스 밖 에 통과하지 못하였다 이후 너비 탐색사용하여 모든 경우의 수를 찾으면서 최소한의 접근이 필요했으며 그 과정속에서 조건에 맞을때 방문 FLAG 변경과 조건2에 부합하는 count를 증가시켜서 최소한의 접근과 모든 경우의 수를 판별하여 newPwd를 찾아 낼수있었다 풀이 코드 : const primePassword = (curPwd, newPwd) => { if(curPwd === newPwd) re..

오름 차순 정렬된 정수의 배열에서 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);..