Doby's Lab

Pollard's Rho를 공부해보기 전에 직접 인수 분해 (소인수 분해) 알고리즘 코드를 작성해봤습니다. #include #include #include using namespace std; vector getPrime(int n){ vector isPrime(n, false); vector ret; for(int i = 2; i n; auto res = factorization(n); // n's factor for(auto factor : res) cout

Miller-Rabin에 대해 공부해봤습니다. 정리까지 끝냈으나 포스팅은 늦어질 거 같아서 코드 먼저 올려두겠습니다. [N의 범위가 int일 때] // Miller-Rabin, N이 int의 범위 일때 #include #include using namespace std; int base[3] = {2, 7, 61}; int power(int a, int k, int mod){ if(k == 0) return 1; else if(k == 1) return a; else{ int value = power(a, k / 2, mod) % mod; if(k % 2 != 0){ return (((value * value) % mod) * (a % mod)) % mod; } else{ return value * va..

https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net Solved By: Divide & Conquer 이러한 출력 문제는 (별 찍기와 비슷함) 어떻게 작동해야 할지는 알겠으나 코드로 짜기는 어렵습니다. 다음 Recursive Call에서 어떤 Parameter로 넘겨주어야 하는지가 제일 까다롭습니다. 항상 별찍기 문제들에서나 실수하던 부분을 이번 문제에서도 실수했었습니다. Divide & Conquer Parameter 실수에 대한 해결법은 항상 ..

https://www.acmicpc.net/problem/17362 17362번: 수학은 체육과목 입니다 2 첫 번째 줄에 19번 문제 세 번째 줄에 등장하는 수 '1000'을 자연수 n으로 바꾸었을 때 그에 해당하는 답의 번호를 출력한다. 즉, 1 이상 5 이하의 자연수 중 하나를 출력해야 한다. www.acmicpc.net Solved By: Math 카테고리가 수학이라 하기엔 제 풀이 방법으로는 좀 애매했습니다. 12 정도까지 했을 때, 나오는 값들 노트에 적어봤습니다. 적어보니 하나의 패턴이 보였습니다. 1 ~ 8까지 '1 2 3 4 5 4 3 2'가 반복되었고, 9 ~ 17까지도 마찬가지입니다. 이 패턴을 활용하기 위해 나머지 연산을 사용하여 문제를 풀 수 있었습니다. 크게 어려운 문제이지 않음..

https://www.acmicpc.net/problem/13237 13237번: Binary tree A binary tree is a mathematical structure made of nodes where each node can have up to two children nodes. One child node will be called left child and the other right child. ch If node B is a child node of A, then we say that A is the parent node of B. In www.acmicpc.net Solved By: DFS #include #include #define MAX 21 using namespace std..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net Solved By: DFS #include #include using namespace std; string board[6][6]; bool visited[6][6]; struct Dir{ int y, x; }; Dir dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int res = 0; set st; void dfs(i..

https://www.acmicpc.net/problem/25372 25372번: 성택이의 은밀한 비밀번호 부산사이버대학교 학생 성택이는 엄마의 의뢰를 받아 주어진 문자열이 현관문 비밀번호에 사용 가능한지 알아내야 한다. 성택이는 공부해야 하므로 우리가 도와주자! 사용할 수 있는 비밀번호 www.acmicpc.net Solved By: T = int(input()) arr = ['' for i in range(0, T)] for i in range(0, T): arr[i] = input() for i in range(0, T): if len(arr[i]) >= 6 and len(arr[i])

https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net Solved By: Primality Test #include #include #include #define MAX 1000000 using namespace std; int T; int n; bool isPrime[MAX]; void fastIO(){ ios_base::sync_with_stdio(false); cin.tie(NULL); } void getPrime(){ memset(isPrime..