yoongrammer

목차펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)펜윅 트리(Fenwick Tree)는 세그먼트 트리의 변형으로 수열의 구간 합을 빠르게 구할 수 있도록 고안된 자료 구조입니다.펜윅 트리는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. 펜윅 트리는 세그먼트 트리처럼 O(logN) 시간으로 구간 합을 구할 수 있으며 세그먼트 트리에 비해 적은 공간이 필요하고 구현하기 쉽다는 장점이 있습니다.펜윅 트리 구성배열 A를 가지고 세그먼트 트리를 만들면 다음과 같습니다. 각 노드에는 구간합 정보가 들어 있습니다.위 세그먼트 트리에서 각 층에에서 짝수 인덱스를 무시하면 아래와 트리를 얻을 수 있습니다.이러한 구조를 펜윅 트리라고 합니다.주어진 n개의 배열..

목차세그먼트 트리(Segment Tree)세그먼트 트리(Segment Tree)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. 다음 예를 보겠습니다.A = {1, 2, 3, 4, 5 … ,N} 라는 배열에 아래 연산을 M번 수행한다고 생각해봅시다.배열의 범위 합을 구하는 Query 연산A[0] + A[1] + A[2] + … + A[N-1]i번째 배열 값을 v로 변경하는 Update 연산A[i] = v단순한 방법으로는 각각 배열에 접근하여 연산을 한다면 시간 복잡도는 1번 연산 O(N), 2번 연산 O(1)이 됩니다.이 두 연산을 M번 수행한다면 총 시간 복잡도는 O(MN)+O(M) = O(MN)이 됩니다. 세그먼트 트리를 사용하면 범위 최소/최대 및 합계 Query 및 범위 Updat..

목차서로소 집합(Disjoint Set) & 유니온 파인드(Union find)서로소 집합(Disjoint Set)Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. Disjoint set 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는 데에 유용하게 사용할 수 있습니다. Disjoint set 자료구조는 MakeSet, Union, Find라는 연산을 제공합니다.MakeSetMakeSet 연산은 주어진 요소만 포함하는 집합을 생성합니다. 이 연산에서 parent 배열을 생성합니다.parent 배열은 노드의 부모 노드를 저장하고 있습니다. 부모 노드가 없다면 자기 자신을 가리킵니다.이 ..

목차그래프 순회 (Graph traversal) 알아보기그래프 순회(traversal)는 모든 정점을 방문하는 작업입니다. 그래프는 탐색하는 동안 동일 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다.동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(Visited)했다는 표시를 하여 중복 방문을 피하도록 합니다. 대표적으로 두 가지 방법이 있습니다.깊이 우선 탐색 (DFS: Depth First Search)너비 우선 탐색 (BFS: Breath First Search)깊이 우선 탐색 (DFS: Depth First Search)깊이 우선 탐색 (DFS: Depth First Search)은 그래프에서 최단 경로를 찾는 간선 기반 알고리즘입니다.DFS는 형제 정점을 탐색하기 전에 ..

목차그래프 표현 및 구현그래프는 일반적으로 두 가지 방식으로 표현합니다.인접 행렬 (adjacency matrix)인접 리스트 (adjacency list)인접 행렬(adjacency matrix)인접 행렬은 그래프를 2차원 배열에 저장하는 방법입니다. 부속된 간선을 찾는 것은 빠르지만 |V| x |V| 만큼의 공간이 필요하여 저장 측면에서 비효율적입니다. (|V| : 정점 수)노드 수보다 간선 수가 많은 dense graph이거나 빠르게 부속(incident)된 간선을 찾을 때 주로 사용합니다.각 행과 열은 정점을 나타냅니다.1. 방향성 그래프 (Directed Graph)방향성 그래프를 인접행렬로 표현하면 다음과 같습니다.각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장합니다.2. 무방향성..

목차그래프 (Graph) 알아보기그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다.정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말함.간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍 (u, v)로 표현함.그래프(G)는 정점들의 집합 V와 간선들의 집합 E를 사용하여 (V, E)로 나타냅니다.G = (V , E)V = {1, 2, 3, 4, 5}E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)}그래프 용어Directed edge & Undirected edge방향성(유향) 간선 (Directed edge)방향을 가진 정점의 쌍 (u, v)으로 화살표로 표현..

목차해시 테이블 (Hash Table) 알아보기해시 테이블(hash table)에 대해 알아보기 전에 Direct address table에 대해 알아보도록 하겠습니다.Direct Address TableDirect address table은 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조입니다. Direct address table은 키 k가 테이블 slot T[k]에 저장되기 때문에 테이블의 크기는 전체 키(U) 개수가 됩니다.위 특징 때문에 direct address table은 중복 키가 없고, 테이블의 크기가 작은 경우에 사용할 수 있습니다. 구현 방법전체 키 집합(U = {0,1 ... ,9})의 크기만 한 테이블(T)을 배열로 만듭니다.실제 사용하는 키 집합(K = {2,3,5,..

목차힙 (Heap) or 이진 힙(binary heap) 알아보기힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조입니다. 힙은 다음과 같은 속성을 가지고 있습니다.완전 이진트리(Complete Binary Tree) 이다.부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음.힙의 종류힙에는 두가지 종류(최대 힙, 최소 힙)가 있습니다. 1. 최대 힙 (Max Heap)부모 키값이 자식노드 키값보다 큰 힙Key(parent) ≥ Key(child)가장 큰 값이 루트..

목차다원 탐색 트리 (Multiway search tree)다원 탐색 트리(Multiway search tree)는 m-원 탐색 트리 (m-way search tree)라고도 합니다. 다원 탐색 트리는 한 노드안에 최대 m-1개의 요소와 m개의 자식을 가질 수 있습니다.이진 탐색 트리는 m=2 인 다원 탐색 트리입니다.다원 탐색 트리의 특징다원 탐색 트리는 다음과 같은 특징이 있습니다. 1. 각 노드는 아래의 개수만큼 서브 트리를 갖습니다.\(0 ≤ 서브트리 개수 ≤ m\)2. k 개의 자식 노드를 가지는 노드는 k-1개의 요소를 갖습니다. (k ≤ m)3. 각 노드 안에 있는 키는 오름차순으로 정렬되어 있습니다.\(key_1 ≤ key_2 ≤ ... ≤ key_{(k-1)}\)4. 다음 조건을 항상 만..

목차AVL 트리(Tree) 개념 및 구현AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다. 트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)입니다.한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 됩니다. AVL트리는 다음과 같은 특징을 가집니다.AVL 트리는 이진 탐색 트리의 속성을 가집니다.왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다.어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다.AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다. Balance Factor(BF)Balance F..