Doby's Lab

https://www.acmicpc.net/problem/4149 4149번: 큰 수 소인수분해 입력은 한 줄로 이루어져 있고, 소인수분해 해야 하는 수가 주어진다. 이 수는 1보다 크고, 262보다 작다. www.acmicpc.net Solved By: Pollard's Rho(Theory(Idea + Floyd's Algorithm, Birthday Paradox) + Miller-Rabin, Exponention By Squaring, Euclidean Algorithm, __int128) 처음으로 폴라드 로 알고리즘을 사용해보았습니다. 폴라드 로 알고리즘을 사용하기 위해 공부해야 할 사전 지식들이 꽤 많습니다. 주말에 Miller-Rabin또한 같이 정리할 것이기에 문제를 풀면서 왜 계속 '시간 ..

https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net Solved By: Sieve of Eratosthenes 내 풀이 (시간 초과) Sieve of Eratosthenes를 사용하여 MAX까지의 소수를 구한 다음, 주어진 N을 prime의 첫 값(2)부터 (n % prime[i] != 0)까지 나누고 나눈 소숫값을 결과에 저장하여 풀었습니다. -> 시간 초과가 나온 이유를 어림짐작해보면 모든 소수를 탐색해서 그런가 싶습니다. 풀이 Sieve of Er..

https://www.acmicpc.net/problem/2857 2857번: FBI 5개 줄에 요원의 첩보원명이 주어진다. 첩보원명은 알파벳 대문자, 숫자 0~9, 대시 (-)로만 이루어져 있으며, 최대 10글자이다. www.acmicpc.net Solved By: string substr(pos, cnt) #include #include #include using namespace std; int main(){ bool flag = true; vector res; for(int i = 1; i > s; for(int j = 0; j < s.length() - 2; j++){ string tmp = s.substr(j, 3); if(tmp == "FBI"){ flag = false; res.push_b..

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..