트리2 [자료구조] Segment Tree(세그먼트 트리) 1. Segment Tree(세그먼트 트리) Segment Tree(세그먼트 트리)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. Segment Tree를 도식화하면, 아래와 같습니다. Segment Tree는 다양한 활용법이 있겠지만, 특히 특정 데이터 배열의 구간 합을 계산할 때 유용합니다. 아래 예시를 통해, 단순 배열 방법과 Segment Tree 활용법을 비교해보겠습니다. 예시 1) 단순 배열 방법 array = {1, 2, 3, ..., N} 배열에서 특정 범위의 구간 합과 특정 인덱스의 값 변경을 M번 수행 (1) array 배열에서 1번째 ~ N번째까지 구간 합 연산S = array[0] + array[1] + array[2] + ... + array[N - 1]시간 복.. 2024. 9. 12. [백준 C++] 14725번: 개미굴 1. 문제https://www.acmicpc.net/problem/14725 2. 알고리즘 분류자료 구조문자열트리트라이 3. 소스 코드#include #include #include #include #include using namespace std;int N, K;struct Trie { map m; // 트라이 삽입 함수 void insert(vector& v, int idx) { // 삽입할 vector 인덱스 넘었을 경우, Return if (idx == v.size()) return; // 새 트라이 할당 및 추가 if (m.find(v[idx]) == m.end()) { Trie* trie = new Trie.. 2024. 6. 9. 이전 1 다음
