알감자의 지식창고 알감자의 지식창고

이번 글에서 다뤄볼 내용은 그래프 탐색 기법 중 하나인 BFS(너비 우선 탐색)입니다. 정의 그래프에서 어떤 노드에 인접한 노드를 모두 탐색한 뒤, 탐색된 노드를 순서대로 접근하여 인접한 노드를 탐색하는 것을 반복하여 탐색하는 알고리즘 동작 과정 현재 노드를 방문처리한다.현재 노드와 연결된 노드 중 방문처리되지 않은 노드를 전부 큐같은 공간에 순서대로 저장한다. 저장된 노드 중 가장 첫번째 노드를 현재노드로 하고 큐에서 제거한다. 1~3을 그래프의 모든 노드를 탐색할 때까지 반복한다. 구현// 시간복잡도는 O(노드수 + 간선수)이다. #include #include #include using namespace std:bool visited[9];vector graph[9];void bfs(int ..

이번 글에서 다뤄볼 내용은 그래프 탐색 기법 중 하나인 DFS(깊이 우선 탐색)입니다. 정의 그래프에서 어떤 노드에 인접한 노드 중 하나를 선택해서 해당 노드와 연결된 노드를 더 이상 탐색할 수 없을 때까지 탐색하는 알고리즘 동작 과정 현재 노드를 방문처리한다.현재 노드와 연결된 노드 중 방문처리되지 않은 노드를 하나 선택한다. 만약 방문처리되지 않은 노드가 존재하지 않는다면 이전 노드로 돌아간다. 선택된 노드를 현재 노드로 한다. 1~3을 그래프의 모든 노드를 탐색할 때까지 반복한다. 구현// 시간복잡도는 O(노드수 + 간선수)이다. #include #include using namespace std:bool visited[9];vector graph[9];void dfs(int x) { visit..

이번 글에서 써볼 내용은 수학에서도 나오는 개념인 에라토스테네스의 체(Eratosthenes Sieve)입니다.  정의 \(2 \leq k \leq \sqrt{n}\) 를 만족하는 \(n\)이하의 모든 \(k\)의 배수들을 제외시켜서 소수를 찾아내는 알고리즘  동작 과정 2부터 \(\sqrt{n}\)까지 순회한다. \(\sqrt{n} * \sqrt{n} = n\)이기 때문에 \(\sqrt{n}\)까지 오는 과정에서 \(n\)이하의 수들은 이미 모든 소수 판별이 끝나있다. 해당 수\((x)\)가 제외된 수인지 아닌지 판단한다. 제외되지 않은 수라면 \(x^2\) 부터 \(x\)를 더하면서 더해진 수를 제외시킨다. \(x\)이전의 수들과 \(x\)를 곱한 수들은 이미 처리가 끝났기 때문에 \(x^2\)부터 ..

오랜만에 PS(Problem Solving)관련된 글입니다. 최근에 백준을 안 풀다보니 실력이 많이 떨어진것 같아서 다시 복습하는 겸 주기적으로 알고리즘을 정리해볼까 합니다.  이번 글은 시작이다보니 쉬운 것부터 해보겠습니다. 이번 글에서 다룰 내용은 누적합(Prefix Sum)입니다.  정의 어떤 수열 A에 대해서 처음부터 각 인덱스까지의 요소들의 합을 미리 구해놓는 알고리즘  누적합을 생성할 때 사용되는 점화식은 아래와 같습니다.\(PrefixSum[i] = PrefixSum[i - 1]  + A[i]\)PrefixSum(누적합의 결과 배열), i(현재 인덱스)   구간합 구하기 누적합의 가장 기본적인 활용법은 구간의 합을 구하는 것입니다. 구간의 합을 구하는 것은 아래의 식을 통해서 할 수 있습니다..

문제 링크https://www.acmicpc.net/problem/17646 사용 알고리즘폴라드 로(Pollard's rho)밀러 라빈 소수 판별법(Miller Rabin Primality Test)Cornacchia's algorithmTonelli-Shanks algorithm 풀이 과정이 문제에서 제곱수의 개수를 구하는 방법은 '제곱수의 합 (More Huge)'와 동일합니다.따라서 이 부분은 생략하고 설명하겠습니다. 먼저 제곱수의 개수가 4인 경우부터 생각해 보겠습니다.제곱수의 개수가 4인 경우는 \(n = 4^a(8b + 7)\) 입니다.그리고 \(4^0(8b + 6)\)은 세 제곱수로 나타낼 수 있기 때문에 이것을 \(x^2 + y^2 + z^2\)이라 하면 다음과 같이 나타낼 수 있습니다.$..

문제링크https://www.acmicpc.net/problem/17633 사용 알고리즘폴라드 로(Pollard's rho)밀러 라빈 소수 판별법(Miller Rabin Primality Test) 풀이 과정먼저 문제를 풀기 전에 아래의 3가지 정리에 대해서 알아야 합니다.페르마의 두 제곱수 정리르장드르의 세 제곱수 정리라그랑주의 네 제곱수 정리각각의 정리에 대한 내용은 다음과 같습니다. 먼저 '페르마의 두 제곱수 정리'는 \(n = 4m + 1\)의 형태를 갖는 모든 홀수 소수는 제곱수 두 개의 합으로 표현된다는 정리이며, 이 정리를 활용해서 임의의 자연수 \(n\)에 대해 \(n = N^2m\) 으로 표현 했을 때 \(m\)에 \(4k + 3\)형태의 수가 포함되지 않으면 \(n\)은 제곱수 두개의 ..

문제 링크https://www.acmicpc.net/problem/17477 17477번: 수열과 쿼리 29길이가 N인 수열 A1, A2, ..., AN이 주어지고, Bi = 0를 만족하는 길이가 N인 수열 B가 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.  1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = Ai + X를 적용한www.acmicpc.net 사용 알고리즘세그먼트 트리(Segment Tree)느리게 갱신되는 세그먼트 트리(Lazy Propagation)세그먼트 트리 비츠(Segment Tree Beats) 풀이 과정문제를 보면 쿼리가 총 4종류가 있습니다.먼저 1번 쿼리의 경우에는 기본적인 Lazy-Propagation을 활용함으로써 쉽게 해결할 수 있습니다. 다음으로 ..

문제 링크https://www.acmicpc.net/problem/14894 14894번: 퀵 소트 cnt++첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 배열 A에 들어있는 수가 공백으로 구분해 주어진다. 주어지는 수는 1부터 N까지의 수로 이루어진 순열이다.www.acmicpc.net 사용 알고리즘세그먼트 트리(Segment Tree)퍼시스턴트 세그먼트 트리(Persistent Segment Tree) 풀이 과정문제를 봤을 때 뭘로 풀어야 할지 감이 도저히 안 잡혀서 태그를 봤더니 PST가 달려있었습니다.PST를 어떻게 써야 이걸 해결할까 생각을 해보니,PST로 kth 트리를 만들고, kth 트리를 통해서 pivot을 구하는 방식이 떠올랐습니다. 결과적으로 여기서 구한 pivo..