개발/알고리즘
확장 유클리드 호제법(Extended Euclidean Algorithm)
확장 유클리드 호제법(Extended Euclidean Algorithm)은 유클리드 호제법의 확장으로 두 정수 $(a,b)$가 주어질 때 $\gcd(a,b)$를 구하고, 또한 정수해를 가지는 방정식 $ax + by = c$의 해 $(x, y)$를 구해주는 알고리즘이다. 베주 항등식의 세 번째 명제에 의해서 $ax + by$는 반드시 $\gcd(a,b)$의 배수이고, 따라서 $c$가 $\gcd(a, b)$의 배수가 아니라면 부정방정식 $ax + by = c$를 만족하는 정수해 $(x, y)$는 존재하지 않는다. $c = \gcd(a,b)$라고 가정할 때, 해 $(x,y)$는 유클리드 호제법의 과정을 따라가면서 구해낼 수 있다. $a,b$에 대해 유클리드 호제법을 돌리는 과정을 식으로 표현하면 다음과 같이..
유니온 파인드(Union-Find)
유니온 파인드(Union-Find), 또는 분리 집합(서로소 집합, Disjoint Set)은 여러 집합들을 표현하는 자료 구조다. Disjoint Set이라는 이름에서도 알 수 있듯이, 이 자료 구조가 표현하는 집합은 서로소이고, 모든 집합의 합집합은 전체집합이다. Union-Find라는 이름은 이 자료 구조가 기본적으로 두 가지 연산, 즉 union과 find만을 지원하기에 붙여진 이름이다. union 연산은 두 집합을 하나로 합치는 연산이고, find 연산은 어떤 원소가 어느 집합에 속하는지 알아내는 연산이다. 초기 상태의 유니온 파인드는 1~N까지의 원소(이건 0-index일 수도 있음)가 전부 크기 1인 집합에 담겨 있다. 여기에서 어떤 두 집합에 union 연산을 수행하면 두 집합이 하나로 합..
트리(Tree)
트리(Tree)는 그래프의 일종이다. 이름의 tree는 나무를 뜻하는 것으로, 꼭 나뭇가지가 위로 뻗어 나가는 형상을 닮았다고 해서 이런 이름이 붙여졌다. 다음 조건을 만족하는 그래프를 트리라고 한다. 연결 그래프이다. 간선의 방향을 무시했을 때 사이클이 존재하지 않는다. 다음 그림에서 1, 2번 그래프는 트리이고, 3번은 트리가 아니다. 3번은 간선의 방향을 무시하면 사이클이 생기기 때문에 트리라고 할 수 없다. 위 두 조건을 만족하는 트리에서는 $E = V-1$이라는 성질을 추가로 가진다. 또한, 트리에서 어떤 두 정점을 잇는 경로는 유일하다. 트리의 구조 트리에서 가장 위에 있는 노드를 루트 노드(Root node) 혹은 루트라고 한다. 루트와 다른 노드 사이의 거리를 그 노드의 깊이(Depth) ..
소수 판정과 소인수분해(Primality Test/Factorization)
소수(Prime number)는 $1$과 자기 자신을 제외한 양의 정수로는 나누어 떨어지지 않는 $1$이 아닌 양의 정수를 의미한다. 소수가 아닌 수를 합성수라고 한다. $1$은 소수도 합성수도 아니다. 소수에는 여러 흥미로운 성질이 있다. 그 중에서 소수 판정과 소인수분해에 쓰이는 중요한 성질로 어떤 합성수 $n$에 대해 $1$이 아닌 $n$의 약수 중 적어도 하나는 $\sqrt{n}$보다 작다는 성질이 있다. 소수 판정 소수 판정(Primality Test)는 어떤 수 $n$이 소수인지 아닌지를 판단하는 문제로, 정수론에서 중요한 문제 중 하나다. 어떤 수 $n$이 소수이려면 $2 \leq k \leq n-1$인 정수 $k$로 나누어 떨어지지 않아야 하므로, $2$부터 $n-1$까지 나눠보면 소수인지..
플로이드 와샬 알고리즘(Floyd-Warshall)
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)은 가중치가 있는 그래프에서 최단 거리를 구하는 알고리즘 중 하나다. 다익스트라나 벨만 포드 알고리즘은 한 정점으로부터 다른 정점까지의 최단 거리를 구하지만, 플로이드 와샬 알고리즘은 모든 정점 쌍 $(i, j)$에 대해 최단 거리를 구해준다. 또한 벨만 포드 알고리즘처럼 음수 간선이 있는 그래프에서도 정상적으로 작동한다. 동작 원리 플로이드 와샬 알고리즘의 동작 원리는 매우 간단하다. 정점 $i$와 $j$의 최단 거리를 계산할 때, 모든 정점 $k$에 대해 $i\rightarrow k \rightarrow j$가 $i \rightarrow j$보다 짧다면 $k$를 경유하는 것으로 최단 거리를 바꾸어 주면 된다. $i$와 $j$가 처음에..
너비 우선 탐색(Breadth-First Search, BFS)
너비 우선 탐색(Breadth-First Search, BFS)는 깊이 우선 탐색과 마찬가지로 그래프의 정점들을 순회하는 알고리즘이다. 깊이 우선 탐색은 될 수 있는 한 끝까지 깊이 들어갔다가 되돌아 오는 반면, 너비 우선 탐색은 시작 정점에서 가까운 정점부터 방문하는 특성을 지닌다. 정확한 동작 방식은 다음과 같다. 시작 정점을 '방문함'으로 설정하고 큐에 삽입 큐에서 가장 앞에 있는 정점과 인접한 정점들을 방문 / 큐에서 가장 앞에 있는 정점 제거 그 정점들을 방문하고 큐에 삽입 모든 정점을 방문할 때까지 2~4를 반복 시각화하면 다음처럼 나타낼 수 있다. 1번 정점을 시작 정점이라고 할 때, 시작 정점과 연결되어 있는 2, 3, 4번 정점을 순서대로 방문한 다음 2번 정점에 연결된 정점, 3번 정점..
깊이 우선 탐색(Depth-First Search, DFS)
그래프에서 깊이 우선 탐색(Depth-First Search, DFS)는 그래프를 탐색하는 방법 중 하나다. 이름에서 알 수 있듯이 DFS는 최대한 깊게 들어갔다가 다시 나오는 탐색 방식이다. 정확한 동작 방식은 다음과 같다. 시작 정점을 방문하고 '방문함'으로 표시 시작 정점과 연결되어 있는 정점 중 아직 방문하지 않는 정점을 시작 정점으로 놓고 1을 반복 연결되어 있고 방문하지 않은 정점이 없다면 이전 정점으로 돌아가 다시 2를 반복 모든 정점을 방문했으면 탐색을 종료 이것을 시각화하면 다음과 같다. 1번 정점을 시작 정점이라고 할 때, 연결되어 있는 정점인 2를 방문하고, 2에서는 5를 방문하고, 다시 돌아와 6, 9... 이런 식으로 방문하기 때문에 총 탐색 순서는 1-2-5-6-9-7-10-3-..
그래프의 정의와 표현
이산수학에서 그래프(Graph)는 정점(Vertex)와 간선(Edge)로 이루어진 집합이다. 기본적으로 위와 같은 형태이며, 간선은 정점 사이를 연결하는 역할을 한다. 또한 정점은 노드(Node)라고도 부른다. 두 정점 $u,v$가 있을 때, $u$에서 $v$로 가는 간선이 있으면 $u$는 $v$와 연결되어 있다고 한다. 어떤 정점에서 시작해서 다시 자기 자신에게 돌아오는 경로가 있다면 그 경로를 사이클(Cycle)이라고 한다. 일반적으로 정점의 개수를 $\vert V \vert$ 혹은 $V$로 나타내고, 간선의 개수는 $\vert E \vert$ 혹은 $E$로 나타낸다. 간선 간선은 정점과 정점을 연결하는 역할이다. 다음과 같은 특성을 추가로 가질 수 있다. 방향(Direction): 특정 방향으로만 ..
유클리드 호제법(Euclidean Algorithm)
어떤 자연수 $n$을 나누어 떨어지게 하는 자연수 $i$를 $n$의 약수라고 하고, $i \mid n$라고 쓴다. 두 자연수 $a, b$의 공통인 약수를 $a, b$의 공약수라고 하고, 가장 큰 공약수를 최대공약수라고 한다. $a,b$의 최대공약수는 $\gcd(a, b)$로 표기할 수 있다. 반대로 $n$으로 나누었을 때 나누어 떨어지는 자연수 $i$를 $n$의 배수라고 한다. 두 자연수 $a, b$의 공통인 배수를 $a,b$의 공배수라고 하고, 가장 작은 공배수를 최소공배수라고 한다. $\text{lcm}(a, b)$로 표기한다. 유클리드 호제법 유클리드 호제법(Euclidean Algorithm)은 유클리드가 기원전 300년경에 만든 인류 최초의 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘이다..
동적 계획법(Dynamic Programming)
피보나치 수열은 다음 점화식을 통해 나타낼 수 있다. $$F_n = \begin{cases} 0 & \text{if }n = 0 \\ 1 & \text{if }n = 1 \\ F_{n-1} + F_{n-2} & \text{if }n > 1 \end{cases}$$ 그대로 재귀함수로 구현하면 다음과 같다. int fibo(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibo(n-1) + fibo(n-2); } 이 함수는 작은 $n$에 대해서는 빠르게 계산된다. 하지만 $50$을 넣으면 1초 안에 답이 나올까? 아마 나오지 않을 것이다. 그러면 입력값에 따른 총 함수 호출 횟수를 계산해보자. int cnt; int fibo(int n) { cnt..