Doby's Lab

https://www.acmicpc.net/problem/15312 15312번: 이름 궁합 영어 대문자 알파벳 26개의 획수는 순서대로 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 로 정한다. (출제자가 알파벳 대문자를 쓰는 방법이 기준이다) www.acmicpc.net Solved By: DP #include #include using namespace std; int base[26] = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1}; int main(){ string a, b; cin >> a >> b; vecto..

https://www.acmicpc.net/problem/19577 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net Solved By: Euler Phi Function xφ(x) = n에서 얻어낼 수 있는 정보는 x는 n의 약수라는 것입니다. 즉, n 이하의 모든 양의 정수를 탐색할 필요가 없다는 뜻입니다. n의 약수를 전부 얻어낼 수 있게 코드를 짭니다. 다음은 Euler Phi를 구현해야 하는데 이전 문제에서는 계속 폴라드 로를 사용해서 구현을 했었는데 소인수의 개수를 알 필요 없이 어떤 소인수만 가지는지 알면 되기 때문에 폴라드 로를 사용하지 않고 구해봅시다. (출처: https://ne..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net Solved By: Sieve of Eratosthenes Sieve of Eratosthenes를 사용하되 체크하는 부분을 sqrt(MAX)까지만 해도 되는 것을 알고서 구현을 해줍니다. 그리고, 방문 배열을 사용하지 않는 코드를 짜서 문제를 풀어봅니다. 왜냐하면 Sieve of Eratosthenes에서 사용했던 num 배열을 다시 한 번 사용하여 n에서 어떤 소수를 뺀..

https://www.acmicpc.net/problem/13926 13926번: gcd(n, k) = 1 자연수 n이 주어졌을 때, gcd(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net Solved By: Pollard's Rho, Euler Phi Function 내 생각 Pollard's rho를 이용해 소인수 분해한 factor들을 구하고, 중복되는 것들은 없애서 1 ~ N까지의 수들을 탐색하며 factor로 나머지가 0으로 나뉘는 것이 있는지 탐색한다. ==> 시간 초과 N이 (1 > N; ull ans = N; if(N == 1){ cout

https://www.acmicpc.net/problem/10854 10854번: Divisions David is a young boy and he loves numbers. Recently he learned how to divide two numbers. David divides the whole day. He is happy if the result of the division is an integer, but he is not very amused if this is not the case. After quite a while he decide www.acmicpc.net Solved By: Pollard's Rho 문제를 읽어보면 알겠지만 이 문제는 N이 주어지면 N의 약수의 개수를 구하는 문..

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