bright jazz music

function naiveSearch(long, short){ var count = 0; for(var i = 0; i

-데이터 셋을 작은 부분으로 나누고 해결을 반복한다. 이러한 방법을 사용하면 시간복잡도가 크게 감소한다.-정렬, 탐색 등 많은 다른 알고리즘에서 사용된다. - 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.  예시: 배열에서 특정 값을 찾는 경우. 선형탐색으로 찾을 수도 있지만 아래처럼 이진탐색 할 수도 있다.function search(array, val) { // 단 배열이 정렬돼 있어야 함 let min = 0; let max = array.length -1; while (min val) { max = middle - 1; } else { return middle; } } ret..

규모가 큰 데이터셋에서 데이터의 하위 집합을 추적하는 문제 있어 유용하다. 배열이나 문자열에서 일련의 데이터를 찾는 경우다.예를 들면 특정 문자열에서 고유한 문자가 연속되어야 하는 경우,"hellothere"--> hel --> el --> l --> lother  또는 배열에서, 일련의 두 원소의 합이 가장 큰 경우를 구하려 할 때maxSubarraySum([1,2,5,2,8,1,5], 2) ==> 10 이런 경우에 윈도우를 하나 만들어야 한다. 이 윈도우는 단일 변수, 하위 배열, 또는 문자열이 될 수도 있다.조건에 따라 이 창문을 이동시킨다. 이동 시작위치와 방향은 자유지만, 일반적으로는 왼쪽(시작점)에서 오른쪽(종료지점)으로 이동한다.경우에 따라 새로운 윈도우를 만들기도 한다. maxSubarra..

한 개의 포인터가 이동하며 조건에 부합하는 값을 찾는 것이 아니라 여러 개의 포인터를 사용하여 값을 찾아내는 방식function sumZero(arr){ for(let i = 0; i  아래는 포인터를 투 개 사용한 투 포인터 방식이다. 포인터를 시작 지점과 끝 지점, 두 개를 사용하여 중앙을 향해 범위를 좁혀오는 방식이다. 단, 배열이 정렬돼 있어야 한다.// 배열이 정렬돼 있어야함.function sumZero(arr) { let left = 0; let right = arr.length - 1; while(left 0) { right--; } else { left++; } }}  예제) 고윳값의 개수다중 포..

빈도수를 세야하는 경우 객체를 활용하면 편리하다.- 문자열과 배열을 반복시킬 때는 for~ of,객체의 속성을 반복시킬 때는 for ~ in 을 사용함에 주의할 것. 빈도수 세기- validAnagram두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 애너그램인지 확인하는 함수를 작성합니다. 애너그램은 다른 글자의 글자를 재배열하여 형성된 단어, 구 또는 이름입니다. (예시: cinema -> iceman)예시:validAnagram('', '') // truevalidAnagram('aaz', 'zza') // falsevalidAnagram('anagram', 'nagaram') // truevalidAnagram("rat","car") // false) // falsevalidAn..

1. 브루트 포스 알고리즘브루트포스 알고리즘- 모든 가능한 경우의 수를 탐색하여 문제를 해결하는 방법이다- 가장 단순하고 직관적인 문제 해결 방식이다- 완전 탐색이라고도 한다장점:- 구현이 쉽고 단순하다- 확실하게 정답을 찾을 수 있다단점:- 시간복잡도가 높다 (대부분 O(n²), O(2ⁿ) 등)- 데이터가 커지면 시간이 기하급수적으로 증가한다간단한 예제// 1. 배열에서 두 수의 합이 target이 되는 조합 찾기function findTwoSum(arr, target) { for(let i = 0; i 브루트 포스가 주로 사용되는 경우:1. 문제의 크기가 작을 때2. 더 효율적인 알고리즘을 찾기 어려울 때3. 여러 알고리즘의 결과를 검증할 때4. 최적화 문제를 해결할 때실제 코딩테스트나 알고리즘..

백트래킹은 가능한 모든 해결책을 탐색하면서, 현재 선택이 잘못된 방향으로 가고 있다고 판단되면 이전 단계로 돌아가서(백트랙) 다른 선택을 시도하는 알고리즘이다. N-Queen 문제를 대표적인 예로 들 수 있다. N-Queen 문제는 체스판 위에 N개의 퀸을 배치하는 문제이다. 어떤 두 퀸도 같은 행, 열, 또는 대각선에 위치하지 않도록 하는 모든 가능한 배치를 찾는 것이다. 만약 같은 행, 열, 대각선에 하나라도 위치하게 된다면 일치한 퀸은 서로가 공격할 수 있는 상황에 노출된다. 이 문제에서는 각 행에 퀸을 배치하면서 이미 배치된 퀸과 충돌하지 않는 위치를 찾는다. 만약 충돌하지 않는 위치가 없다면 그 행에 대한 배치를 포기하고 이전 행으로 돌아가 다른 위치를 시도한다. 이러한 방식을 시도하면 모든 가..

탐욕법(Greedy Algorithm)은 각 단계에서 그 순간에 최적이라고 생각되는 선택을 하는 알고리즘이다.  탐욕법의 주요 특징:단순성: 구현이 비교적 간단다지역적 최적: 각 단계에서 최적의 선택을 한다빠른 실행: 일반적으로 실행 속도가 빠다주의할 점:탐욕법이 항상 최적의 해를 보장하지는 않다특정 문제에만 적용 가능하다탐욕법이 잘 동작하는 다른 예제들:회의실 배정 문제크루스칼 알고리즘(최소 신장 트리)허프만 코딩 가장 대표적인 탐욕법 예제가 "거스름돈 문제"이다. function getChange(amount) { // 사용 가능한 동전들 (큰 단위부터 정렬) const coins = [500, 100, 50, 10]; const result = []; for (l..

동적 프로그래밍은 하나의 문제를 여러 개의 작은 문제로 나누어 해결하고 해당 결과를 저장한 후에 더 큰 문제를 해결할 때 사용하는 방법론이다. 따라서 알고리즘이라기보다는 문제 해결 방법론으로 보는 관점도 있다. 동적 프로그래밍은 개발자의 관점에서 볼 때, '큰 문제'에 중점을 두어야 한다. '큰 문제'가 있어야 동적 프로그래밍의 효율성이 극대화 된다. 즉, 동적계획법은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 특징:작은 문제의 해결책을 저장(메모이제이션)하여 재사용중복 계산을 피함으로써 성능 향상상향식(bottom-up) 또는 하향식(top-down) 방식으로 구현 가능피보나치 수열을 예로 들어 보면,// 일반적인 재귀 방식 (비효율적): n이 커질수록 함수가 재귀적으..

깊이우선탐색과 너비우선탐색은 그래프 데이터를 탐색하는 강력한 두 가지 알고리즘이다. 이 두 방식의 초점은 정점(vertex 또는 node)에 있다. 모든 정점을 순회하거나 정점 사이의 최단 거리를 찾아내는 것이다. 반면 최소신장트리는 정점을 이어주는 '간선'을 위한 알고리즘이라 할 수 있다.  MST는 아래의 경우 주로 사용된다.네트워크 설계 (최소 비용으로 모든 지점 연결)도로 건설 (최소 비용으로 모든 도시 연결)전기 회로 설계파이프라인 설계네트워크 비용 계산 및 최적화:통신망을 배치할 때마다 얼마나 비용이 들어갈 수 있는지 계산할 수 있다. 이는 최소신장트리가 간선 가중치의 합이 최소인 트리를 구성할 수 있기 때문이다. 효율적 전력망:A에서 B까지 전기를 보내야 할 때 가장 빠르고 저렴한 공급 경로..