끄적끄적

목차 추가 메서드의 전체 코드는 다음과 같다.import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;class Main { static class Node { Map childNode; boolean endOfWord; public Node() { this.childNode = new HashMap(); this.endOfWord = false; } } static class Trie { Node root; Trie(Node node) { th..

목차 트라이 (Trie/Prefix Tree)데이터(주로 문자열)을 효율적으로 저장하고 탐색하기 위한 자료구조이다.검색을 뜻하는 단어 Retrieval 에서 유래되었으며, 트리 형태로 이루어져있다.접두사를 기반으로 동작하기에, Prefix Tree라고도 불린다.   적용 사례  "아이"라는 키워드를 검색했을 때, 해당 단어를 접두사로 하는 모든 단어를 표시해준다.이렇듯 접두사를 활용할 수 있는 자동완성 기능, 자연어 처리(NLP), 맞춤법 검사기(Spell Checker)등에 사용된다. 트라이의 특징1. 접두사(prefix)를 기반으로 문자열을 저장한다.node라는 문자열을 저장하면, 해당 문자열과 함께 접두사인 n, no, nod또한 저장된다. (node 또한 node의 접두사이다.)밑에 등장하지만, ..

목차 세그먼트 트리(Segment Tree)완전 이진 트리에 기반한 자료구조이다.고정된 크기의 수열에서 특정 구간의 질의 및 수정을 효율적으로 수행하기 위해 사용한다. 세그먼트 트리의 필요성길이 N=100만인 배열에서 특정 구간의 합을 구해야한다고 가정해보자. 최악의 경우는 아마, 전체 원소의 합을 구하는 경우일 것이다. 이는 O(100만)이 소요된다.수정의 경우는 어떨까? 해당하는 인덱스의 값을 변경하면 된다. 이는 O(1)이 소요된다. 세그먼트 트리를 사용한다면, 연산과 수정을 O(logN)에 수행할 수 있다. 즉, O(log100만=19.93)이다.합을 구하는 동작을 m번 수행한다면, 더 엄청난 차이가 발생할 것이다. 유의할 점이진수에 기반한 컴퓨터 과학에서, log의 밑은 e가 아닌 2를 의미한다..