A collection of 92 articles on programming, technology and life.
Concept 여러 노드들을 그룹으로 묶고 특정 노드들이 같은 그룹인지 판단하는 알고리즘이다. Union(노드들을 그룹으로 묶는 과정)과 Find(특정 노드들을 같은 그룹인지 판단하는 과정)으로 나눌 수 있다. Union Find로만 해결할 수 있는 문제는 거의 없다. Union Find는 여러 문제를 해결하기 위한 보조 도구로 많이 사용된다. 시간복잡도는 최적화 여부 및 순서에 따라 다르지만 경로 압축을 하지 않은 Union Find는 노드의 개수를 n이라 할 때 최대 $O(n)$이 걸린다. 경로 압
Concept Node 값에 배열의 범위를 가진 이진 Tree Struct의 일종이다. 는 말 그대로 배열(Array)의 범위를 말한다.ex) $[0:n-1]$, $[2:3]$, $[(n-1)/2+1:n]$ 보통 배열의 범위 구간의 합, 차, 곱을 빠르게 계산할 때 사용한다. 배열의 길이를 N이라 하고 쿼리(구간 연산을 계산하는 횟수)를 M이라고 할 때, $O(logN)$의 시간복잡도가 소요된다. Segment Tree 원리 배열의 길이를 N이라 할 때 Segment Tree의 ro
Concept Spanning Tree는 그래프에서 Node의 개수가 n이라고 했을 때 모든 Node들이 (n-1)개의 Edge로 연결되어 있는 Tree를 뜻한다. Spanning Tree는 [[DFS(Depth-First Search)]]나 [[BFS(Breadth-First Search)]]로 Node을 탐색하며 구할 수 있다. 이때 Spanning Tree는 사이클이 포함되서는 안된다. Minimum Spanning Tree는 Nodes에 연결되어 있는 Edges 중 Cost를 고려하여 Spanning Tr
Concept [[Segment Tree]]형태로 각 노드의 값은 해당 노드의 구간에 있는 원소들이 정렬된 List값을 가진다. Leaf Node는 하나의 원소만 가지고 있으며 Parent Node로 올라가며 각각의 Node의 원소들을 합치면 된다. 합치는 과정에서 각각의 Node들의 원소들은 정렬되어 있기 때문에 Merge방식으로 정렬할 수 있으며 이는 $O(logN)$의 시간복잡도가 소요된다. (n : 정렬할 원소 개수) Merge Sort Tree 원리 [[Segment Tree]] 구조를 가지
Concept Tree에서 두 노드(v, u)가 있을 때, 그 두 노드의 최소 공통 조상을 찾는 알고리즘이다. LCA 구하는 방법에는 여러가지 방법이 있다. 두 노드의 깊이를 맞춘 다음 한 칸씩 올라가며 공통 조상을 찾는 방법 $O(n)$ : 1번 방법과 유사하지만 한 칸씩 올라가는 것이 아닌 [[DP(Dynamic Programming)]]을 이용해 2^i만큼 올라가며 조상을 비교하는 방법 $O(log_{N})$ : 2번 방법이 시간복잡도면에서