하루 알고리즘(JS)

[바미] Tree algorithms - AVL trees 알고리즘.

AVL trees AVL 트리는 균형 이진 탐색 트리의 일종으로, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리를 말합니다. AVL 트리에서 각 노드의 높이 차이를 재조정하는 연산을 회전(rotation)이라고 하죠. 그래서 AVL 트리에서 균형을 유지하기 위해 각 노드의 두 자식 서브트리의 높이 차이(높이 균형 인수)는 -1, 0, 1 중 하나여야 하는데 만약 높이 균형 인수가 이 범위를 벗어난다면 해당 노드를 불균형 상태로 판단하여 회전 연산을 수행해 균형을 유지하게 되죠. 코드 구현 AVL 트리의 구현을 위해 다음과 같은 노드 구조체가 필요한데요. class AVLNode { constructor(value) { this.value = value; this.left = ..

[바미] Graph algorithm - 최소 신장 트리(Minimum Spanning Tree, MST) 구현하기

최소 신장 트리? 최소 신장 트리(Minimum Spanning Tree, MST)는 가중치 그래프에서 모든 노드를 포함하면서, 간선의 가중치 합이 최소인 트리를 의미하는데요. 이를 구하는 알고리즘으로는 Prim's Algorithm과 Kruskal's Algorithm이 있습니다. Prim's Algorithm Prim's Algorithm은 시작 정점에서부터 출발하여 신장 트리 집합을 확장해 나가는 방법입니다. Kruskal's Algorithm Kruskal's Algorithm은 간선들을 가중치 순으로 정렬한 후에 사이클을 형성하지 않는 선에서 차례대로 선택하는 방법입니다. 이제 Prim's Algorithm과 Kruskal's Algorithm을 구현해 볼까요? Prim's Algorithm 구..

[바미] Graph algorithm - Dijkstra의 최단 경로 알고리즘 구현하기.

Dijkstra의 최단 경로 알고리즘? Dijkstra의 최단 경로 알고리즘은 그래프에서 출발점에서부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘인데요. 이 알고리즘은 음의 가중치를 가진 간선을 허용하지 않아요. 음의 가중치 음의 가중치(negative weight)는 그래프에서 간선의 가중치가 음수인 경우를 말하는데 일반적으로 Dijkstra의 최단 경로 알고리즘은 음의 가중치가 없는 그래프에서 사용되고 있어요. 그 이유는 음의 가중치가 있는 경우에 최단 경로를 찾는 문제에서 최적해가 아닐 수 있기 때문이죠. 음의 가중치가 있는 그래프에서 시작 노드와 도착 노드 사이의 최단 경로를 찾는 문제를 생각할 때 만약 음의 가중치가 있는 경로가 최단 경로가 되는 경우, Dijkstra 알고리즘은 최단 경로..

[바미] Dynamic programming - 0/1 Knapsack Problem 알고리즘 구현하기.

Knapsack problem? Knapsack problem은 동적 계획법을 이용하여 효율적으로 해결할 수 있는데요. 이를 위해서는 다이나믹 프로그래밍의 개념을 이해해야 합니다. 다이나믹 프로그래밍(Dynamic Programming)은 복잡한 문제를 간단한 하위 문제로 나누어 해결하는 알고리즘인데 중복되는 하위 문제들을 한 번만 계산하여, 전체 문제를 해결하는 효율적인 방법을 제공합니다. Knapsack problem의 경우, 각 아이템을 배낭에 넣거나 넣지 않을 수 있으므로, 하위 문제는 아이템을 넣을지 말지에 따라 달라지죠. 따라서, 각 아이템마다 넣을지 말지에 대한 선택지를 가지고, 모든 가능한 선택지에 대해서 최대 가치를 계산해야 해요. 이 때, 각 선택지에 대한 최대 가치는 이전 선택지에 대..

[바미] Dynamic programming - LCS 알고리즘 구현하기.

Longest Common Subsequence? Longest Common Subsequence (LCS) 알고리즘은 주어진 두 개의 문자열에서 가장 긴 공통 부분 문자열을 찾는 알고리즘입니다. 여기서 부분 문자열이란, 원래 문자열의 일부 문자들을 순서대로 골라 만든 새로운 문자열을 말하는데 예를 들어, "ABCDGH"와 "AEDFHR" 두 문자열이 있다고 가정해보죠. 이 두 문자열에서 가장 긴 공통 부분 문자열은 "ADH"가 되죠? 이 때, "ADH"는 "ABCGD"와 "AEDFHR"의 부분 문자열이지만, "ACF"는 "ABCGD"와 "AEDFHR"의 부분 문자열이 아니게 돼요. LCS 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)을 활용하여 구현됩니다. 구체적으로, 두 문자열 ..

[바미] Search algorithm - Breadth-first search 알고리즘 구현하기.

BFS(Breadth-First Search)? BFS(Breadth-First Search)는 그래프 자료구조에서 사용되는 탐색 알고리즘 중 하나로, 너비 우선 탐색이라고도 불립니다. 이 알고리즘은 루트 노드에서 시작하여 인접한 모든 노드를 방문한 후에, 그 노드들의 인접한 노드를 차례대로 방문하는 방식으로 탐색을 진행합니다. BFS는 큐(Queue) 자료구조를 사용하여 탐색을 수행합니다. 우선 시작 노드를 큐에 넣고, 큐가 빌 때까지 다음의 과정을 반복합니다. 큐에서 하나의 노드를 꺼냅니다. 해당 노드의 인접한 노드들을 방문합니다. 방문한 노드를 큐에 넣습니다. 이러한 과정을 반복하여, 모든 노드를 방문할 때까지 탐색을 진행합니다. 이렇게 탐색된 노드들의 순서는 노드들의 거리 순서대로 정렬되며, 각 ..

[바미] Search algorithm - Depth-first search 구현하기

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 =..

[바미] Search algorithm - Binary search 구현하기.

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

[바미] Sorting algorithm - Heap sort 구현하기.

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]]..