개발일지

개념 If p is prime and a is an integer not divisible by p, then 문제 16134 조합 www.acmicpc.net/problem/16134 16134번: 조합 (Combination) \(\begin{pmatrix}N\\R\end{pmatrix}\)의 값을 1,000,000,007로 나눈 나머지를 출력하자! (단, 1,000,000,007은 소수이다) www.acmicpc.net 코드 #include using namespace std; constexpr long long MOD = 1000000007; long long pow(long long x, long long y) { long long result = 1L; while (y) { if (y & 1)..

개념 강한 연결 요소(Strongly Connected Component)는 방향 그래프에서 서로 왕복할 수 있는 가장 큰 정접들의 집합입니다. 작동원리 1. DFS를 하면서 방문하는 순서대로 값을 할당하고, 스택에 넣는다. 2. DFS를 하면서 방문하지 않는 정점이나, 방문했지만 아직 SCC에 속하지 않은 정점들에게 할당된 값 중 가장 작은 값을 리턴한다. 3. 자신에게 할당된 값과 리턴값이 같으면 SCC이다. * 타잔 알고리즘은 스택을 사용하여 SCC를 추가하기 때문에 위상정렬이 된다. 시간복잡도 1. DFS할 때 O(V + E) O(V + E) 문제 2150 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Conne..

개념 강한 연결 요소(Strongly Connected Component)는 방향 그래프에서 서로 왕복할 수 있는 가장 큰 정접들의 집합입니다. 작동원리 1. 정방향 그래프로 DFS를 하면서 탐색이 끝나는 순으로 스택에 넣는다. 2. 스택에서 하나씩 꺼내면서 역방향 그래프로 DFS를 진행한다. 3. 역방향으로 DFS를 진행하면서 방문하는 정점들이 SCC이다. 시간복잡도 1. 정방향 그래프로 DFS -> O(V + E) 2. 역방향 그래프로 DFS -> O(V + E) O(V + E) 문제 2150 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000..

개념 단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 작동원리 DFS를 이용하여 정점이 몇 번째로 방문되는지 기록하고, 기록한 값 중에 최솟값을 반환한다. DFS를 통해 반환된 값들 중 자신보다 큰 값이 있으면 단절선이다. (아직 방문하지 않았다는 뜻으로, 지금 보는 정점이 아니면 갈 방법이 없다는 뜻, 즉 지금 보는 간선을 제거하면 그래프가 분리된다.) 시간복잡도 DFS를 할 때 O(V + E) 문제 11400 단절선 www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다..

개념 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 작동원리 DFS를 이용하여 정점이 몇 번째로 방문되는지 기록하고, 기록한 값 중에 최솟값을 반환한다. - DFS를 시작한 Root일 경우 DFS를 통해 갈 수 있는 정점이 2개 이상일 경우 단절점이다. (Root를 통해 갈 수 있다는 정점이 2개 이상이면 Root를 제거했을 때 그래프가 2개 이상으로 분리된다는 뜻이다.) - DFS를 시작한 Root가 아닐 경우 DFS를 통해 반환된 값들 중 자신보다 크거나 같은게 있으면 단절점이다. (자신보다 값이 크거나 같은게 있다면, 아직 DFS를 통해 방문하지 않은 정점이 있다는 뜻이고, 자신이 없을 경우 방문하지 못하기 때문에 그래프가 분리된다는 뜻이다.) 시간..

개념 Lowest Common Ancestor의 약자로써 트리에서 가장 가까운 공통 조상을 찾는 알고리즘이다. 쉬운 방법으로 두 노드의 높이를 맞추고 하나씩 올라가면서 검사하는 방법이 있다. -> O(n) 시간 복잡도를 줄이는 방법 ancestor라는 2차원 배열을 만들고, ancestor[index][i] = index의 2^i 위에 부모노드를 저장하고 높이를 올릴 때 2^n단위로 올린다. -> O(logn) ancestor[index][i] = ancestor[ancestor[index][i - 1][i - 1] 작동원리 1. DFS를 사용하여 각 노드의 Level과 ancestor배열을 초기화한다. 2. 높이가 깊은 노드의 높이를 2^n 단위로 올리면서 맞춘다. 3. 두 노드가 같은 뿌리에 있으면 ..

개념 Convex Hull이란 2차원 평면 위에 점들이 있을 때 최소한의 정점으로 다른 정점들을 감싸는 알고리즘이다. 대표적인 알고리즘으로 Graham's Scan(그라함 스캔)이 있다. 작동원리 1. 정점을 반 시계 or 시계 방향으로 정렬한다. 2. Graham's Scan 알고리즘을 이용한다. 시간복잡도 정점을 정렬할 때 -> nlogn, Graham's Scan할 때 -> n -> O(nlogn) 문제 1708 블록 껍질 www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋..

개념 Counter Clock Wise 알고리즘의 줄임말이다. 세 점의 외적의 성질을 이용하는 알고리즘으로 보통 세점의 방향이 시계, 반시계, 직선인지 판별한다. 또한 외적의 성질을 이용하여 세 점이 이루는 삼각형의 넓이를 알 수 있다. 작동원리 세 점을 크로스 곱하여 그 값이 양수면 반 시계, 0이면 직선, 음수면 시계방향이다. 크로스 곱하여 2로 나누면 세 점이 이루는 삼각형의 크기이다. 시간복잡도 세 점을 외적할 때 -> 1 -> O(1) 문제 11758 CCW www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2,..