0. 세그먼트 트리(Segment Tree)란?세그먼트 트리(Segment Tree)어떤 데이터가 주어질 때, 특정 구간의 결과값(구간합, 최댓값 등)을 구하는데 사용하는 자료구조세그먼트 트리는 이진 트리(Binary Tree) 구조를 가지고 있으며, 특정 구간의 결과값을 시간복잡도 O(logN)으로 빠르게 구할 수 있다는 장점이 있다.또한, 자료의 수정이 빈번히 일어날 때, 사용한다. 이 게시글에서는 누적합을 구하는 세그먼트 트리 기준으로 설명을 한다.만약 구간 최대나 구간 최소를 알고 싶다면, 반환하는 부분만 수정하면 된다.1. 세그먼트 트리 알아보기1-1. 세그먼트 트리 생성(초기화)아래는 [5, 7, 6, 3, 1, 9]인 원본 배열로부터 만든 세그먼트 트리이다.파란 글씨는 해당 노드가 가리키는 ..

0. 트라이(Trie)트라이(Trie)는 문자열을 저장하고 호율적으로 탐색하기 위한 트리 형태의 자료구조이다. 트라이는 Retrieval Tree에서 나온 단어로 검색할 때 사용되는 자동완성 기능, 사전 검색 등 문자열 탐색에 특화되어 있다.단, 각 노드에서 자식들에 대한 배열을 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다.(메모리 복잡도에서 비효율적임)0-1. 트라이 자료구조의 노드 구조트라이의 노드는 4개의 정보를 담고 있다.key: 현재 노드의 알파벳data: 현재 노드까지의 결과 -> 완성된 문자열endOfWord: 현재 노드로 이루어진 단어가 있는지 판단하는 변수children: 자식 알파벳 노드들1. 트라이(Trie) 연산1-1. 삽입첫번째 문자가 trie head의 자식 노드에 있는..

0. 힙(Heap)완전 이진 트리에 있는 노드에서 가장 큰 키 값이나 가장 작은 키 값을 찾기 위해서 만든 자료구조이다.중복 값도 가능하다.힙의 특징으로는 노드의 삽입 혹은 삭제 연산이 발생할 때만, 해당 노드가 옳바른 자리를 찾아간다.0-1. 최대 힙(Max Heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 >= 자식 노드의 키 값루트 노드: 키 값이 가장 큰 노드0-2. 최소 힙(Min Heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 루트 노드: 키 값이 가장 작은 노드1. 힙 연산최대 힙을 기준으로 설명을 할 예정이며, 최소 힙의 경우도 동일하게 동작한다.노드 하나의 삽입 / 삭제 연산은 시간 복잡도가 O(lonN)이고 최대값/최소값을..

0. 그래프그래프는 아이템과 이들 사이의 연결 관계를 표현하는 자료구조이다.그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조이다.정점(Vertex): 그래프의 구성요소로 하나의 연결점간선(Edge): 두 정점을 연결하는 선차수(Degree): 정점에 연결된 간선의 수인접(Adjacency): 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.경로(Path): 어떤 정점에서 시작하여 다른 정점으로 끝나는 순회로 두 정점 사이를 잇는 간선들을 나열한 것싸이클(Cycle): 경로의 시작 정점과 끝 정점이 같음(시작한 정점에서 끝나는 경로)V개의 정점을 가지는 무향 그래프는 최대 V * (V-1) / 2개의 간선이 가능하다.선형 자료구조나 트리..