프로그래밍(Basic)

[바미] Pattern matching algorithms - Knuth-Morris-Pratt 알고리즘 구현하기.

Knuth-Morris-Pratt? Knuth-Morris-Pratt 알고리즘은 문자열 검색 알고리즘 중 하나로, 특정 문자열에서 패턴 문자열을 찾는 알고리즘이에요. 이 알고리즘은 패턴 문자열의 길이와 검색 문자열의 길이에 비례하는 시간복잡도를 가져서 대용량의 문자열에서 효율적으로 검색할 수 있죠. 동작 방식 패턴 문자열을 전처리하여 접두사(prefix)와 접미사(suffix)의 최대길이를 구해요. 검색 문자열을 순회하며 패턴 문자열을 비교해요. 만약 일치하지 않는 문자가 있다면, 해당 문자가 포함된 접미사와 접두사를 이용하여 패턴 문자열을 이동시켜요. 이동한 패턴 문자열과 검색 문자열을 다시 비교해줘요. 일치하지 않는 문자가 없을 때까지 위 과정을 반복해요. 그럼 이제 구현해볼까요? 코드 구현 func..

[바미] Hash tables - Open addressing알고리즘 구현하기

Open addressing? Open addressing은 충돌이 발생하면 해시 테이블 내의 다른 빈 슬롯에 데이터를 저장하는 기법인데요. Open Addressing 방식에서는 해시 충돌이 발생했을 때, 선형 탐사, 제곱 탐사, 이중 해싱 방법으로 충돌을 해결하는데요. 이것들에 대해 알아보자면 Linear Probing (선형 탐사) 해시 충돌이 발생하면, 다음 인덱스를 탐사하며 빈 공간을 찾아요. 탐사하는 인덱스는 hash(key) + i (i는 0, 1, 2, ...)와 같이 계산하죠. Quadratic Probing (제곱 탐사) 선형 탐사의 단점을 보완하기 위해, 제곱 값을 이용해 탐사하는 방법인데 탐사하는 인덱스는 hash(key) + i^2 (i는 0, 1, 2, ...)와 같이 계산해요...

[바미] Hash tables - chaining 알고리즘 구현하기.

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

[바미] Tree algorithms - Trie trees 구현하기.

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

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

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

[바미] 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의 경우, 각 아이템을 배낭에 넣거나 넣지 않을 수 있으므로, 하위 문제는 아이템을 넣을지 말지에 따라 달라지죠. 따라서, 각 아이템마다 넣을지 말지에 대한 선택지를 가지고, 모든 가능한 선택지에 대해서 최대 가치를 계산해야 해요. 이 때, 각 선택지에 대한 최대 가치는 이전 선택지에 대..