승형님의 블로그

선분 L1과 L2가 주어졌을 때, 두 선분이 교차하는지 판정하는 알고리즘. typedef pair pii; pair L[2]; int func(pair L1, pair L2); int CCW(pii A, pii B, pii C); int func(pair L1, pair L2) { pii p1 = L1.first, p2 = L1.second, p3 = L2.first, p4 = L2.second; int ccw1 = CCW(p1, p2, p3) * CCW(p1, p2, p4); int ccw2 = CCW(p3, p4, p1) * CCW(p3, p4, p2); if (ccw1 == 0 && ccw2 == 0) { if (p1 > p2) swap(p1, p2); if (p3 > p4) swap(p3, p4)..

2차원 좌표평면에 세 점 $p_1, p_2, p_3$가 주어질 때, 다음 식을 통해 $p_1 \to p_2 \to p_3$로 형성되는 선분의 방향성을 알 수 있다. 벡터의 외적 $S = (x_1y_2 + x_2y_3 + x_3y_1) - (x_2y_1 + x_3y_2 + x_1y_3)$ $if $ $ S 0$, 반시계방향 int CCW(pair A, pair B, pair C) { int a = A.first * B.second + B.first * C.second + C.first * A.second; int b = B.first * A.second + C.first * B.second + A.first * C.second; ..

$p_1, p_2, ... p_k$를 $N$의 소인수라고 할 때, Euler's phi function에 의해 다음이 성립한다. $\Phi (N) = N \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2})\times ... \times (1 - \frac{1}{p_k}) $ 이때, $\Phi(N)$은 1 이상 $N$이하의 수 중 $N$과 서로소인 수의 개수를 의미한다. $p_1, p_2, ... p_k$는 모두 $N$의 소인수이기 때문에 결과값은 항상 정수임을 확인할 수 있다. 이를 구현하면 다음과 같다. 수를 소인수 분해 한 뒤, 소인수들로 식을 형성한다. https://int-p.tistory.com/21 정수의 소인수분해 알고리즘 정수 K를 소인수분해하여..

정수 K를 소인수분해하여 다음과 같이 나타낼 수 있다. $K = p_{1}^{q_{1}}\times p_{2}^{q_{2}}...\times p_{i}^{q_{i}}\times M$ 이때, $p_{1}, p_{2} ... p_{i} \leq \sqrt{K}$ 이고, M은 소수이다. int K; vector primeFact; int main(void) { cin >> K; for (int i = 2; i * i

다익스트라 알고리즘을 활용하여 최단경로를 구할 때, 최단경로의 길이 뿐만 아니라 정확한 경로를 역추적 해야하는 필요성을 느낄 때가 있다. 기본적인 다익스트라 알고리즘은 다음과 같은 과정으로 이루어진다. 1. dist[i](시작정점 S에서 i로 가는 최단경로 값) 배열을 INF로 초기화한다. 2. 시작정점인 dist[S]를 0으로 초기화하고, 정점과 그 정점까지의 거리 {거리, 정점}을 우선순위 큐에 넣어준다. 3. 거리가 작은 순으로 우선순위가 구성된 우선순위 큐에서 값을 하나씩 꺼내며 기존 dist[vertex]보다 값이 작거나 같은 경우 작업을 수행한다. 4. 현재 정점 now와 인접한 임의의 정점을 next라고 할 때, 현재 정점에 연결된 간선을 모두 조사하며 dist[next] 배열을 더 작은 값..

정렬(Sorting)은 항목들을 특정한 순서(예: 오름차순, 내림차순)에 따라 배열하는 것을 말한다. 데이터를 정렬하여 보관하면, 데이터의 검색(Searching)이 용이해 문제의 복잡도를 크게 감소시킬 수 있다. 데이터를 정렬하는 방법에는 여러 가지가 있는데, 병합 정렬(Merge Sort)는 분할 정복(Divide-and_Conquer)의 방식으로 데이터를 정렬하며 O(N log N)의 시간 복잡도로 수행된다. 우선 배열의 처음 인덱스와 끝 인덱스의 절반을 기준으로 배열의 왼쪽 영역과 오른쪽 영역을 나누어준다. 이렇게 배열의 크기를 계속해서 분할하여 각각의 크기가 1이 되었을 때, 합치는 작업을 수행하며 정렬을 진행한다. 데이터를 분할하는 과정은 다음과 같이 재귀적으로 이루어진다. // C/C++로 ..