Algorithm

[Java] 트라이(Trie) 알고리즘

트라이(Trie) 알고리즘 개요 정렬된 배열에서 특정 정수 값을 찾기 위한 시간 복잡도는 $O(\log N)$ (N은 배열의 크기)이다. 예를 들어서 1~64 까지 임의의 수를 찾기 위한 최대 시도 횟수는 6번이다. 그러면 문자열을 찾기 위한 시간 복잡도는 어떻게 될까? 문자열을 찾기 위해서 각 문자마다 어디에 위치하는지 찾아야 한다. 이는 $O(\log N)$의 연산을 하고, 문자열의 길이가 M이라고 했을 때, 총 시간 복잡도는 $O(M\log N)$이 된다. 하지만 트라이 알고리즘을 사용한다면, 내가 원하는 원소를 $O(M)$만에 할 수 있다. (공간과 시간의 Trade Off를 이용..) 트라이 알고리즘은 트리를 이용하여 구현한다. 각 원소마다 HashMap이 존재하여 다음 문자의 위치로 이동하는 ..

[Java] 프림 최소 스패닝 트리

프림 최소 스패닝 트리 도입 스패닝 트리 보통 '신장 트리' 라고 알려진 이 트리 형태는 사이클이 없고 모든 정점이 연결된 형태의 트리이다. 대표적으로 크루스칼, 프림 2가지 방식이 있는데 여기서는 프림만 다룬다. 크루스칼 알고리즘은 여기저기 만들어진 트리 조각들을 합쳐서 스패닝 트리를 만드는 반면, 프림 알고리즘은 하나의 시작점으로 구성된 트리에 간선을 추가하는 방식이다. 시간 복잡도 그냥 단순히 정점을 추가할 때 마다 간선을 검색한다면 $O(|E||V|)$ 의 시간 복잡도를 갖으나, 최적화를 통해 $O(|V|^2+|E|)$ 가 될 수 있다. 알고리즘 시작점을 기준으로 트리에 추가할 정점을 추가 기존 트리에 존재하지 않으면서, 가중치가 가장 작은 간선 선택 선택된 정점으로부터 기존 정점(u)까지 최저비..

3.4 MANIPULATING BIG-O

3.4 MANIPULATING BIG-O 171. Prove that if $f_i(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$, then $f_1(n) + f_2(n) = O(g_1(n)+g_2(n))$. $$ \begin{aligned} f_1(n) &\leq c_1 \cdot g_1(n) \\ f_2(n) &\leq c_2 \cdot g_2(n) \\ \end{aligned} $$ 일 때 $$ \begin{aligned} f_1(n) + f_2(n) = O(g_1(n)+g_2(n)) \\ f_1(n) + f_2(n) \leq c(g_1(n)+g_2(n)) \end{aligned} $$ 를 증명하자 $$ \begin{aligned} f_1(n) + f_2(n) &\leq ..

3.1 RANK THE FUNCTIONS

3.1 RANK THE FUNCTIONS 98 Consider the following eighteen functions: $\sqrt{n}$ $n$ $2^n$ $n\log n$ $n-n^3+7n^5$ $n^2+\log n$ $n^2$ $n^3$ $\log n$ $n^{1/3}+\log n$ $(\log n)^2$ $n!$ $\ln n$ $n/\log n$ $\log \log n$ $(1/3)^n$ $(3/2)^n$ $6$ Group these functions so that f(n) and g(n) are in the same group if and only if f(n) = O(g(n)) and f(n) = O(f(n)), and list the groups in increasing order. 1...

2.7 FIBONACCI NUMBERS

2.7 FIBONACCI NUMBERS The Fibonacci numbers $F_n$ for ($n \geq 0$) are defined recursively as follows: $F_0 = 0, F_1 = 1$, and for $n \geq 2, F_n = F_{n-1} + F_{n-2}$ 52 Prove by induction on n that $\sum_{i=0}^{n}F_i = F_{n+2} -1$ 52-1. Basis Condition n = 0일 때 성립하는가? $$ \begin{aligned} F_{2} &= F_1 + F_0 \\ &= 1 + 0 = 1 \\ \end{aligned} $$ $$ \begin{aligned} \sum_{i=0}^{n}F_i &= F_{n+2} -1 \\ ..

러시아 농부 곱셈법

러시아 농부 곱셈법 A * B 연산이 있을 때 A는 계속 2배로 하고 B는 계속 1/2배로 해서 B가 1이 될때 까지 반복한 결과가 곱셈의 답이 된다는 알고리즘이다. 설명 B가 짝수일 때 $A_B = (A_2) * (B/2)$ B가 홀수일 때 $A_B = (A_2) * (B/2) + A$ 여기서 나누기 연산은 나머지를 버리는 연산이고, 부족한 A만큼을 채워준다고 생각하면 쉬울 것이다. 따라서 B가 홀수일 때는 A만큼을 더해준다. 증명 A*B 연산을 러시아 농부 곱셈법을 이용해서 한다고 하자. 러시아 농부 곱셈법 함수를(Russian Farmer) RF(A,B)라고 하자. 1. 초기값 증명 B가 1일 때 B가 1이 될 때 까지 반복하는 것이므로 바로 종료 따라서 $RF(A,B)$는 A가 답이 된다. B가 ..

2.4 DIVISIBILITY

2.4 DIVISIBILITY 24 Prove by induction on $n \geq 0$ that $n^3 + 2n$ is divisible by 3 24-1. Basis Condition n = 0일 때 성립하는가? $$ \begin{aligned} n^3 + 2n \mod 3 &= n^3 + 2n - 3 \lfloor \frac{n^3+2n}{3} \rfloor \\ 0 \mod 3 &= 0 - 3 \lfloor 0/3 \rfloor \\ &= 0 \end{aligned} $$ 이므로 성립한다. 24-2. Induction (귀납 가정) n = k일 때 성립한다고 가정하자. $$ \begin{aligned} n^3 + 2n \mod 3 &= n^3 + 2n - 3 \lfloor \frac{n^3..

[Java] 상호 배타적 집합

상호 배타적 집합 개요 ㄹ 두 원소가 같은 트리에 속했는가? -> 각 원소가 포함된 트리의 루트를 찾은 뒤 이들이 같은 지 비교 if 루트가 같다면 두 노드가 같은 트리에 속함 else 루트가 다르다면 두 노드가 다른 트리에 속함 -> 합치기 연산 시행 루트 노드는 자기 자신을 가리킴 static class DisjointSet { // parent : 각 노드의 부모 위치 Vector parent; // rank : 각 노드의 높이 Vector rank; public DisjointSet(int n) { parent = new Vector(); rank = new Vector(); // 노드 수 만큼 반복 for (int i = 0; i < n; i++) { // 처음은 자기 자신이 부모 parent...

[Java] 크루스칼 최소 스패닝 트리

크루스칼 최소 스패닝 트리 도입 스패닝 트리 보통 '신장 트리' 라고 알려진 이 트리 형태는 사이클이 없고 모든 정점이 연결된 형태의 트리이다. 대표적으로 크루스칼, 프림 2가지 방식이 있는데 여기서는 크루스칼만 다룬다. 알고리즘 모든 간선을 가중치의 오름차순으로 정렬 간선을 트리에 추가 (단, 사이클이 생기는 간선은 고려 제외) 사이클이 생기는 것을 어떻게 판단하는가? -> 상호 배타적 집합 자료구조 사용 동작 과정은 다음과 같다. 코드 import java.util.Comparator; import java.util.Vector; public class 크루스칼_최소_스패닝_트리 { static class DisjointSet { // parent : 각 노드의 부모 위치 Vector parent; ..

[Java] 위상정렬 알고리즘

개요 위상정렬은 의존성이 있는 작업들이 주어질 때 어떤 순서로 수행해야 하는지 계산하는 알고리즘이다. 예를 들어서 A, C 가 끝나야 B를 작업한다고 하자. 이 경우에 탐색 순서를 A->C->B or C->A->B 순으로 해야한다. 위상 정렬의 특징은 그래프 내 사이클이 없는 방향그래프라는 점이다. 위상 정렬을 구현하는 방법은 깊이 우선 탐색의 응용 들어오는 간선이 하나도 없는 정점을 하나씩 찾아서 지우는 방식 2가지가 있다. 구현 1. 깊이 우선 탐색의 응용 import java.util.Vector; public class 깊이_우선_탐색 { // 그래프의 인접 리스트 표현 static Vector adj; // 각 정점을 방문했는지 여부를 나타낸다. static Vector visited; // 결..