Algorithm/Data Structure
[Algorithm] 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)
[Algorithm] 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)
2023.04.07펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)? 펜윅 트리는 세그먼트 트리의 변형으로 세그먼트 트리보다 메모리를 더 절약할 수 있다. 또, 갱신을 O(log n)의 시간에 수행할 수 있으며, 세그먼트 트리보다 구현이 쉽다는 장점이 있다. 구성 펜윅트리는 일반적인 세그먼트 트리와 다르게 기존 배열과 같은 크기로 구성할 수 있다. 펜윅 트리는 다음과 같이 구성한다. 여기서 노란 블럭은 기존 배열, 초록 블럭은 트리 배열이다. 0이 아닌 최하위 비트 펜윅 트리를 초기화하고 업데이트하기 위해선 값을 어떻게 인덱싱하는지 알아야한다. 이때, 0이 아닌 최하위 비트 값을 더해주는 방식을 취한다. 먼저 각 비트의 0이 아닌 최하위 비트를 구하는 방법을 알아보자. 예를 들어 3, 6,..
[Data Structure] 트라이 트리(Trie Tree)
[Data Structure] 트라이 트리(Trie Tree)
2023.03.19트라이 트리(Trie Tree)? 트라이 트리는 문자열 검색을 빠르게 해주는 트리 형태의 자료구조이다. radix tree, prefix tree, retireval tree 라고도 한다. 여기서 트라이(Trie)는 retireval에서 따온 단어이다. 구현 위 그래프 처럼 car, cb, do, dog라는 단어를 저장한다고 가정한다. 먼저 노드를 하나 만들어 주어야 한다. import java.util.HashMap; import java.util.Map; public class Node { private final Map children; private boolean endOfWord; public Node() { children = new HashMap(); } public Map getChildr..
[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree)
[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree)
2023.02.14신장 트리(Spanning Tree)? Spanning Tree는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 특징 DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 최소 신장 트리(MST, Minimum Spanning Tre..
[Data Structure] 세그먼트 트리(Segment Tree)
[Data Structure] 세그먼트 트리(Segment Tree)
2022.09.08세그먼트 트리? 여러 개의 데이터가 존재할 때 특정 범위의 합을 구하는데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진트리의 형태이다. 0 1 2 3 4 5 6 7 8 9 5 6 9 3 8 2 5 1 4 7 위의 데이터에서 1부터 7까지의 합을 구한다 했을 때, 일반적으로 데이터를 하나씩 돌면서 더하면 O(N)의 시간이 걸린다. 하지만 세그먼트 트리를 사용하면 O(logN)의 시간에 구할 수 있다. 구현 세그먼트 트리 생성 먼저 전체 원소를 더한 값을 최상단 노드에 넣는다. 이때, 최상단 노드의 인덱스는 1을 부여한다. 트리를 구현하다보면 알겠지만, 양쪽 자식노드의 인덱스를 부여할 때 0부터 시작하는 것보다 1부터 시작하는 것이 편하다. 왼쪽자식노드 = 부모노드*2, 오른쪽자식노드 = 부모노드 * ..
[Data Structure] 이진 탐색 트리(Binary Search Tree)
[Data Structure] 이진 탐색 트리(Binary Search Tree)
2022.08.17이진 탐색 트리(Binary Search Tree)? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. 각 노드에 중복되지 않는 키가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 서브 트리는 각각이 다시 이진탐색트리여야 한다. 이진탐색트리는 이진탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조이다. 이진탐색트리(BST)는 이진탐색의 빠른 탐색 시간과 연결리스트의 빠른 삽입/삭제의 장점들을 가져왔다. 이진탐색은 탐색 시간이 O(log n)으로 빠르지만 삽입/삭제가 불가능하다. 또 연결리스트의 경우, 삽입/삭제는 O(1)이지만..
[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap)
[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap)
2022.08.17우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐의 요소는 모두 우선순위를 가지고 있으며, 우선순위가 같은 경우에는 큐의 순서에 따라 처리한다. 우선순위 큐는 여러 방식으로 구현할 수 있지만 힙(heap)이 가장 효율을 보이기 때문에 일반적으로 힙을 이용하여 구현한다. 방식 시간 복잡도 배열 O(N) 연결 리스트 O(N) 힙 O(logN) 힙(heap) 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드는 자식노드 사이에 대소관계를 가지고 있다. 중복된 키를 허용한다. 힙의 종류 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙 최소 힙(min heap): ..