하루 알고리즘(JS)

chaining? 해시 테이블에서 충돌이 일어나면 chaining 알고리즘을 사용하여 충돌을 해결할 수 있는데, 이 알고리즘은 연결 리스트 를 사용하여 충돌된 데이터를 저장합니다. Chaining을 구현하기 위해서는 먼저 해시 테이블과 연결 리스트가 필요합니다. 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 키를 해시 함수에 입력하여 버킷 인덱스를 계산하고, 해당 버킷에 값을 저장합니다. 연결 리스트는 각 버킷에 저장되는 데이터를 연결하여 저장하는 자료구조입니다. 코드 구현 해시 함수 구현 해시 함수는 키 값을 버킷 인덱스로 변환하는 함수입니다. 이번 예제에서는 간단한 해시 함수를 구현하여 사용해보겠습니다. function hashFunction(key, size) { let hash = 0; for ..

Trie tree? Trie tree는 문자열 검색을 효율적으로 수행하기 위한 트리 자료구조입니다. 이진 트리와는 달리 한 노드당 여러 개의 자식 노드를 가지며, 각 자식 노드는 해당 위치에 올 수 있는 문자를 나타내는 것이 특징이죠. 코드 구현 class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let current = this.root; for (let i = 0; i < word.length; i++) { let ch = word.charAt(i); let node = cu..

LIS알고리즘? Longest Increasing Subsequence (LIS) 알고리즘은 어떤 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘을 말하는데요. 예를 들어, 수열 [3, 1, 5, 2, 4, 9]에서 LIS는 [1, 2, 4, 9]이 되죠. LIS 알고리즘은 동적 프로그래밍 기법을 사용하여 해결할 수 있는데 문제를 해결하기 위해 각 요소에 대한 최장 증가 수열의 길이를 계산하고, 최종적으로 이들 중 최대 값을 찾아주죠. 먼저 Bottom-up 방식으로 LIS 알고리즘을 구현해 보겠습니다. 이 방식에서는 DP table을 채우기 위해 이전 값들을 사용하는 방식으로 구현됩니다. Bottom-up 방식 코드 구현 function longestIncreasingSubsequence(nums..

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

최소 신장 트리? 최소 신장 트리(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 구..

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

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

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

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