이진 탐색(Binary Search) 개념 배열 및 리스트를 반으로 나누어 탐색 범위를 줄여나가는 식으로 동작하는 알고리즘 대용량의 데이터 처리에 효과적 이진탐색을 구현하기 위한 배열 및 리스트는 반드시 정렬 되어 있어야 함. 이진탐색 구현법 정렬된 배열, start 인덱스, end 인덱스 배열을 반으로 나누었을때 경우의 수 3가지 중간 값이 찾고자하는 값과 같을때 - 검색성공을 return 중간 값이 찾고자하는 값보다 작을때 - 반으로 나눈 왼쪽 요소를 이진탐색 중간 값이 찾고자하는 값보다 클때 - 반으로 나눈 오른쪽 요소를 이진탐색 복잡도 O(log n) 이진 검색 알고리즘 풀이 function binarySearch(states, target) { let left = 0; let right = st..

검색 알고리즘 많은 사람들이 구글을 떠올릴것입니다. 구글이 사용하는 알고리즘은 매우 까다롭고 세상에서 가장 어려운 알고리즘중 하나일것입니다. 많은 부분이 계속해서 변경됩니다. 개인정보 사용기록 등등.. 클릭한 것들에 따라 알고리즘이 엄청나게 변화한다는것은 알고 있을것 입니다. 제가 강아지를 검색한 결과와 다른사람이 검색한 결과는 다를 것인것 처럼요. 문자열이 있는데 해당 문자열에 포함 된 다른 문자열이있는지 확인을하는경우를 예로들수있습니다. 혹은 다른사람들이 회원가입을 하는 경우라던가. 사용자명이 사용중인지 알려줘야 하기 때문입니다. 배열에 대한 검색 미국의 주가 포함된 배열이 있다고 가정하겠습니다. const usStates = [ "Alabama", "Alaska", "Arizona", "Arkans..

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 n번째 피보나치 수를 출력한다. 예제 입력 10 예제 출력 55 정답 let input = require("fs").readF..

재귀함수란? 자기자신을 호출하는 함수를 의미합니다. 일반적인 함수처럼 입력값을 받고, 그 입력값에 대한 연산을 하면서 결과값을 반환할 수 있습니다. 재귀함수는 함수내에서 자신을 호출하면서 작업을 반복적으로 수행하며, return keyword 즉,연산을 반복적으로 수행중 원하는 반환값이 나온다면 종료되도록 하는 함수입니다. 자바스크립트에서는 HTML의 DOM트리의 특성인 중첩된 div를 재귀함수를 통해 보다 쉽게 접근 할 수 있습니다. // 재귀함수를 사용하여 특정 클래스명을 가진 모든 DOM 요소를 찾는 함수 function findElementsByClassname(className, node) { node = node || document.body; // 시작 노드가 주어지지 않으면 body를 시작..

분할과 정복? 분할과 정복 알고리즘이란, 엄청나게 큰 문제를 나누어서 해결한 뒤, 합쳐서 문제를 해결한다는 뜻에서 분할과 정복 알고리즘이라고 불립니다. 대표적으로는 퀵정렬,병합정렬이 있습니다. 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눕니다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복합니다. 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합합니다. 분할과 정복 알고리즘의 장점? 문제를 나누어 풀어가며 어려운 문제를 쉽게 해결 할 수 있다(효율적으로)는 장점이 있습니다. 그리고, 재귀적인 방법을 사용하기 때문에 알고리즘의 구현이 간결하고 이해하기 쉽습니다. '병렬적'으로 문제를 풀이하는 강력한 알고리즘중 하나입니다. 분할과 정복 알고리즘의 단점? ..

다중 포인터 패턴은 공식이름이 아닙니다. 다중 포인터 패턴 배열이나 리스트와 같은 데이터 구조에서 특정 조건을 만족하는 요소를 찾거나 조작하는데 사용되는 알고리즘 기법. 한쌍의 값이나 조건을 충족 시킨다는 개념만 알면 됨. 두가지의 참조값을 사용한다. [1,2,3,4,5,6,7] "asdfasdgaaxvasdFF" 두가지의 참조값을 설정하여 어느 한 곳으로 이동시키며 비교한다. 서로를 향하든 혹은 서로를 향하지 않고 한곳으로 이동하든. 예시 sumZero([-3,-2,-1,0,1,2,3]) // [-3,3] sumZero([-2,0,1,3]) // undefined sumZero([1,2,3]) // undefined sumZero라는 함수는 정렬된 배열을 가진 함수입니다. 1번째 배열에서 -3 3을 더..

빈도수 세기 패턴? 어떠한 문자열 및 배열을 빈도수체크 방식으로 풀이함 방식 원래는 중첩 for문을 이용하여 풀이하였지만 시간복잡도에서 O(n^2)의 시간 복잡도를 보였기 때문에, 효율적인 알고리즘이 아니라고 판단하였고 빈도수 세기 패턴을 이용하여 시간 복잡도를 줄였다. 문제 두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 애너그램인지 확인하는 함수를 작성합니다. 애너그램은 다른 글자의 글자를 재배열하여 형성된 단어, 구 또는 이름입니다. 예시 validAnagram('', '') // true validAnagram('aaz', 'zza') // false validAnagram('anagram', 'na..

문제 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다. 이런 상근이를 불쌍하게 보던 창영이는 자신이 사용하는 방법을 추천해 주었다. 바로 "45분 일찍 알람 설정하기"이다. 이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다. 현재 상근이가 설정한 알람 시각이 주어졌을 때, 창영이의 방법을 사용한다면, 이를 언제로 ..