bright jazz music

BFS는 그래프나 트리 구조에서 노드를 탐색하는 알고리즘으로, 루트 노드(혹은 시작 노드)에서 시작하여 인접한 노드들을 먼저 탐색하는 방식이다. 주요 특징:큐(Queue) 자료구조를 사용같은 레벨(depth)에 있는 노드들을 먼저 탐색최단 경로를 찾는 문제에서 많이 사용됨BFS의 실제 활용 사례:최단 경로 찾기 (예: 네비게이션)웹 크롤링SNS에서 친구 추천 시스템네트워크 탐색아래 코드는 A 노드에서 출발하여 BFS를 하는 과정을 출력한다.// 그래프를 인접 리스트로 표현const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E']};function..

깊이우선 탐색은 그래프나 트리 구조에서 가능한 한 깊이 탐색하다가, 더 이상 탐색할 수 없을 때 다른 경로로 돌아가서 탐색을 계속하는 알고리즘이다. DFS의 주요 특징:한 방향으로 끝까지 탐색한 후 다음 경로를 탐색한다.재귀 또는 스택을 사용하여 구현할 수 있다.시간 복잡도는 O(V + E)입니다. (V: 정점 수, E: 간선 수)DFS의 활용 사례:미로 찾기위상 정렬연결 요소 찾기순환 감지경로 찾기실제로 사용할 때는 방문한 노드를 표시하는 것이 중요하며, 무한 루프를 방지하기 위해 visited 세트를 사용한다. // 인접 리스트를 사용한 그래프 구현const graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], '..

이진탐색은 데이터를 반으로 나눠가면서 데이터를 찾는 방식을 뜻한다.이진탐색은 특성상 데이터가 정렬된 상태여야 한다. 데이터가 정렬된 상태라면 아래의 순서로 진행한다. 1단계: 전체 배열의 중간 인덱스의 원소와 검색값을 비교한다.2단계: 검색값이 배열의 좌우 중 한 곳에 포함되면 다시 1단계를 반복한다. 즉, 중간을 자르고 크기를 비교하는 것을 반복하는 것이 이진탐색 알고리즘이며, 선형탐색보다 검색 횟수가 적기 때문에 시간 복잡도에서 우위가 있다. // 중앙 값을 구해서 나머지를 버린다.(이 때문에 mid가 left값과 더 가까울 수 있음)// 배열에서 mid인덱스 값이 타겟값인 경우 리턴한다.// mid인덱스 값이 타겟보다 작으면 mid에 1을 더한 값을 left에 할당한다. 새로 만들 mid값을 오..

모든 데이터를 찾아 보는 가장 단순하면서도 직관적인 방법이다. //pnpm exec ts-node codeTest.tsconst dictionary = [ { word: 'a', mean: '라틴 문자의 첫 번째 글자' }, //...];function findMean (keyword, array) { for (let i = 0; i el.word === 'a');console.log(result?.mean);// 라틴 문자의 첫 번째 글자 하나의 반복문을 돌면서 주어진 값이 나올 때까지 검색하는 방식이다. 그러므로 선형 탐색의 시간 복잡도는 O(n)이라 할 수 있다. 자바스크립트에서는 선형 탐색을 사용해 배열에서 원하는 값을 반환받는 메서드가 존재한다. Array.prototype.find() 이..

자바스크립트에서는 기본적으로 정렬 함수를 제공한다. 가장 대표적인 정렬 메서드는 Array.prototype.sort()이다. 이 메서드는 기본적으로 모든 배열에 사용할 수 있고, 아래와 같은 방식으로 사용한다. const array1 = [5, 7, 2, 9, 6, 13];const array2 = ['red', 'blue', 'yellow', 'green']console.log(array1.sort());console.log(array2.sort());/*[ 13, 2, 5, 6, 7, 9 ][ 'blue', 'green', 'red', 'yellow' ]*/ 배열에 sort() 메서드를 호출하면 호출한 배열이 정렬된다. 원소가 숫자 또는 문자인 경우 모두 쉽게 정렬이 가능하다. 따라서 실제로는 정렬..

기수 정렬은 자릿수를 기반으로 정렬한다.가령 숫자의 일의 자리, 십의 자리, 백의 자리와 같은 자릿수이다. 당연히 두 자리 숫자는 한 자리 숫자보다 크고 세 자리 숫자보다 작다.보통 기수 정렬은 10진수를 기반하여 설명하고 사용하지만 원리를 이해하면 다른 진법에서도 적극적으로 활용하 수 있다. 기수 정렬의 작동 순서1단계: 가장 작은 자릿수부터 가장 큰 자릿수까지 반복하여 비교한다.(값 그 자체가 아니라 자릿수를 비교함에 주의)2단계: 각 자릿수를 기준으로 입력 배열을 정렬한다.3단계: 각 자릿수별로 정렬된 배열을 합쳐 정렬을 완료한다.function radixSort(arr) { // 최대값 찾기 const maxNum = Math.max(...arr); // 현재 자릿수 (1의..

힙 정렬은 최댓값, 최솟값을 찾는 데 특화된 정렬 방법이다. 해결해야 할 문제가 최대, 최솟값을 찾아내는 것이라면 힙 정렬을 사용해야 할 수도 있다. 힙(heap):힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)이며 힙 속성을 만족한다. 완전 이진 트리(complete binary tree):완전 이진트리는 각각의 노드가 최대 "두 개"의 자식 노드를 가지는 트리 자료구조이다. 가장 위에 존재하는 노드를 루트 노드(root node)라고 한다. 이진트리에는 레벨이 존재한다. 루트 노드가 위치하는 가장 상단 레벨부터 Level 0 이다. 내려갈수록 레벨이 증가한다.이진트리에..

퀵 정렬은 비교 정렬에 속한다. 비교 정렬이란 버블 정렬과 같은 분류인데, 버블정렬이 자신의 다음 인덱스의 원소와 비교해 정렬해 나가는 것처럼 퀵 정렬은 피벗(pivot)을 선택하여 비교 기준점을 만들고 비교하며 정렬을 진행한다. 퀵 정렬은 3단계로 진행된다. 1단계: 배열 중 원소 하나를 선택한다. 이 원소를 피벗이라고 한다.2단계: 피벗 앞에는 피벗보다 작은 값의 원소를 두고, 피벗 뒤에는 값이 큰 원소들이 오도록 배열을 '분할'한다. 분할 후 피벗의 위치는 변경되지 않는다.분할된 2개의 작은 배열에 대해 앞의 과정을 반복한다. 배열의 크기가 0 또는 1이 될 때까지 반복한다. 퀵 정렬과 합병정렬은 유사해 보이지만 차이가 있다. 합병정렬은 언제나 배열을 균등하게 절반으로 나누어 비교하지만, 퀵 정렬은..

합병(병합)정렬은 분할 정복 알고리즘 중 하나이며, 일반적으로 데이터의 안정성을 훼손하지 않는다.분할 정복은 크게 3단계로 구성된다. 1) 분할(Divide): 최소단위까지 문제를 분할한다.2) 정복(Conquer): 최소 단위 문제를 각각 해결하여 정복한다.3) 결합(Combine): 최소 단위 문제에 대한 결과를 원래 문제에 대한 결과로 조합하여 해결한다. 분할-정복의 3단계:1단계: 배열을 계속해서 반으로 자른다. 원소가 1개가 될 때가지 자른다.2단계: 자른 순서의 역순으로 한 쌍씩  값을 비교하여 합쳐간다.3단계: 하나의 배열이 될 때까지 2단계 과정을 반복한다. function mergeSort(arr) { // 배열의 길이가 1 이하면 정렬이 필요없으므로 그대로 반환 if (arr..

while문을 사용한 삽입정렬의 일반형 function insertionSort(arr) { for (let i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr;}   for문을 사용하는 경우 아래와 같다.function insertionSort(arr) { for (let i = 1; i = 0 && arr[j] > key; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = key; } return arr;}  오름차순 삽입정렬 로직을 가지고 있는, 배열을 파라미터로 받는 함수의 경우 아..