하루 알고리즘(JS)

DFS(깊이 우선 탐색)은 그래프 탐색 알고리즘 중 하나로, 루트 노드(시작 노드)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 가능한 한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 루트로 탐색하는 방법입니다. function DFS(graph, start) { const visited = {}; for (let i = 0; i < graph.length; i++) { visited[i] = false; } DFSUtil(start, visited, graph); } function DFSUtil(vertex, visited, graph) { visited[vertex] = true; console.log(vertex); const neighbors =..

바이너리 서치는 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 코드 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left

Heap sort는 선택 정렬 알고리즘을 발전시킨 것으로, 최대/최소 값을 빠르게 찾을 수 있는 이진 트리(Heap)를 이용하여 정렬하는 알고리즘입니다 코드 function heapSort(arr) { // 최대 힙 구성 function heapify(arr, i, n) { var parent = i; var left = 2 * i + 1; var right = 2 * i + 2; if (left arr[parent]) { parent = left; } if (right arr[parent]) { parent = right; } if (parent !== i) { // 부모 노드와 자식 노드 교환 [arr[i], arr[parent]]..

function mergeSort(array) { if (array.length

function quickSort(arr) { if (arr.length

안녕하세요. 오늘은 최소 신장 트리에 대해 알아보도록 하겠습니다.Spanning Tree란?그래프 내의 모든 정점을 포함하는 트리를 말합니다.Spanning Tree = 신장 트리 = 스패닝 트리입니다.Spanning Tree는 그래프의 최소 연결 부분 그래프입니다.최소 연결 = 간선의 수가 가장 적습니다.n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 됩니다.그러므로, 그래프에서 일부 간선을 선택해서 만든 트리가 되죠.Spanning Tree의 특징DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있습니다.탐색 도중에 사용된 간선만 모으면 만들 수 있습니다.하나의 그래프..