Algorithm/Data Structure5 [자료구조] 트라이(Trie) 트라이(Trie)는 문자열을 저장하고 빠르게 탐색하기 위해 사용되는 트리 형태의 자료구조입니다. 각 노드는 문자를 나타내며, 문자열의 접두사를 공통으로 가지는 경로를 형성합니다. 구현 저는 다음과 같이 구현하였습니다. #include using namespace std; typedef struct node { char c = '\0'; bool is_word; vector children; }; struct Trie { node root; node *_insert(node *rt, const char *s) { if (s[0] == '\0') { rt->is_word = true; return rt; } for (node *child : rt->children) { if (child->c == s[0]).. 2023. 5. 18. [자료구조] sparse table 치토스 선배 강의 듣고 씀. 희소 테이블(sparse table) 희소 테이블(sparse table)은 배열 내 구간의 쿼리를 빠르게 수행할 수 있는 자료구조이다. 배열 arr[0, ..., N-1]이 아래와 같이 있다고 가정하고, i ~ j 구간에 대한 쿼리의 결과(예를 들어 구간 합)를 function(i, j)라고 두면 우선 sparse table 배열 d[i][0]에는 function(i, i) = arr[i]가 들어간다. 그 후 d[i][k]에는 function(i, i + 2^k - 1)이 들어간다. 이를 표로 그리면 아래처럼 된다. 즉 d[1][3]에는 1번 원소부터 시작해서 2^3 = 8개 원소의 합이 저장되어 있다. 만약 2~7 구간의 합을 구하고 싶다면, 이는 2~5 구간의 합 + 6.. 2020. 10. 9. [자료구조] 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 부분 합을 트리 구조에 저장해서, 값이 바뀔 수 있는 상황에서도 부분합을 빠르게 구할 수 있는 방법이다. 세그먼트 트리를 그려보면 이런 느낌이다. 위의 대괄호 안에 들어있는 숫자는 각 노드의 인덱스이고, 아래 큰 숫자는 부분합의 범위이다. 즉 루트 노드인 [0]에는 배열의 0~9번째 값들의 합이 저장되어 있고, [11] 노드에는 배열의 5~6번째 값들의 합이 저장되어 있는 식이다. 구현 | 1. init 배열의 초기 값을 세그먼트 트리에 처음 넣는 함수이다. 이때는 루트 노드 [0]부터 아래로 내려간다. 한 노드에 값을 채울 때는 자식 노드에 값을 먼저 채우고 그 뒤에 그 합을 쓰면 되는 것이다. 그런 식으로 말단 노드 (예를 들어, 6번째부터 6번째까지의 합 노.. 2020. 4. 14. [자료구조] 큐(Queue) 큐(Queue) | 한 쪽 끝에서는 자료를 넣고, 반대쪽 끝에서는 자료를 뺄 수 있는 선형 자료구조. FIFO(First-In-First-Out) | 먼저 들어간 자료가 먼저 나온다. 인큐(Enqueue) | 큐에 자료를 넣는 것. 디큐(Dequeue) | 큐에서 자료를 빼는 것. 사이즈(Size) | 큐의 크기. 큐에 들어 있는 자료 수. 프론트(Front) | 큐의 가장 앞에 있는 자료. 백(Back) | 큐의 가장 뒤에 있는 자료. 2019. 11. 11. [자료구조] 스택(Stack) 스택(Stack) | 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조. LIFO(Last-In-First-Out) | 먼저 들어간 자료가 나중에 나온다. 푸시(Push) | 스택에 자료를 넣는 것. 팝(Pop) | 스택에서 자료를 빼는 것. 사이즈(Size) | 스택의 크기. 스택에 들어 있는 자료 수. 탑(Top) | 스택의 가장 위에 있는 자료. (접근 가능한 자료.) 2019. 11. 3. 이전 1 다음
tokki
