트라이(Trie) 알고리즘 트라이는 문자열들을 저장하고 효율적으로 탐색할 수 있는 트리 기반의 자료구조입니다. 특히, 자동 완성, 사전 검색 등의 기능에 유용하게 사용됩니다. 기본 구조 트라이의 각 노드는 알파벳을 키로 가지는 자식 노드들의 맵(또는 배열)과, 문자열의 끝을 나타내는 플래그로 구성됩니다. 1. 트라이 노드 정의 class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } 2. 트라이 클래스 정의 class Trie { constructor() { this.root = new TrieNode(); } // 문자열 삽입 insert(word) { let node = this.root; for (let ch..
크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘은 그래프에서 최소 비용 신장 트리를 찾기 위한 알고리즘입니다. 주요 아이디어는 간선의 비용을 기준으로 오름차순 정렬한 후, 가장 작은 비용의 간선부터 연결하되 사이클을 형성하지 않도록 주의하는 것입니다. 아래는 크루스칼 알고리즘의 기본 개념을 사용하여, 그래프에서 최소 비용 신장 트리의 총 비용을 구하는 자바스크립트 함수입니다. class UnionFind { constructor(size) { this.parent = Array.from({ length: size }, (_, index) => index); } find(node) { if (this.parent[node] === node) { return node; } return this.paren..
그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘은 현재 상황에서 가장 최선의 선택을 하는 방식으로 문제를 해결하는 방법론입니다. 이 알고리즘이 항상 최적의 해를 구하는 것은 아니지만, 특정 문제들에 대해서는 빠르게 근사적인 해답을 찾을 수 있습니다. 예시로 많이 사용되는 거스름돈 문제를 살펴봅시다. 문제: 손님에게 N원을 거슬러주어야 할 때, 가지고 있는 동전의 종류는 500원, 100원, 50원, 10원이며, 손님에게 동전의 개수를 최소로 하여 N원을 거슬러 주어야한다. 동전의 개수를 구하시오. 1. 일반적인 방법 주어진 동전들을 어떤 방식으로든 조합하여 N원을 만들 수 있습니다. 하지만, 그렇게 하면 경우의 수가 많아져서 계산이 오래 걸릴 수 있습니다. 2. 그리디 알고리즘 활용 f..
