개발일지

문제 설명 제한 사항 및 입출력 예제 개념 이 문제는 주어진 문자열에서 추출 가능한 모든 숫자 조합 중 소수가 몇 개 있는지를 찾는 문제다. 이 문제를 해결하기 위해서는 두 가지 주요 과정이 필요하다. 먼저 가능한 모든 숫자 조합을 생성해야 한다는 것이다. 이 과정에서 문자열의 순열을 찾는 개념을 사용한다. 즉, 주어진 문자열의 모든 문자를 사용하여 만들 수 있는 모든 숫자 조합을 배열에 담는다. 두 번째는 소수를 판별하는 것이다. 생성된 모든 숫자 조합을 순회하며 소수인지 판별한다. 문제를 해결하는 과정에서 주의해야 할 점은 동일한 숫자가 두 번 이상 카운트되면 안 된다는 점이다. 예를 들어 "11"은 "1"이 두 번 등장하므로 소수인 11이 두 번 카운트되어서는 안 된다. 이 문제는 중복을 허용하지 ..

문제설명 입출력 예제 개념 주어진 정수 N(짝수)을 두 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제다. 예를 들어, 10을 입력하면 10 = 3 + 7, 5 + 5로 2개가 출력된다. 이때 소수의 순서만 다른 것은 같은 파티션인 것에 유의하자. 문제의 시간 제한이 매우 빡빡하기 때문에, 에라토스테네스의 체 알고리즘을 사용하여 주어진 범위 내의 소수를 미리 구한 후, 구한 소수들을 활용하여 문제를 해결할 수 있다. 이러한 알고리즘은 시간 복잡도가 O(Nlog(log(N))) 으로 매우 빠르다. 풀이 #include #include #include using namespace std; const int n = 1000000; vector isprime(n + 1, true); int main() ..

문제설명 입출력 예제 개념 자연수 n과 2n 사이의 소수의 개수를 출력하는 문제다. O(sqrt(N)) 보다 조금 더 세밀한 시간 조정이 필요하다. 풀이 #include using namespace std; bool IsPrime(long long num) { if (num N; if (N == 0) break; for (int i = N + 1; i

문제설명 입출력 예제 개념 주어진 범위 내의 소수를 찾는 문제다. 이전에 포스팅했던 소수 찾는 알고리즘을 활용하면 쉽게 풀 수 있다. 풀이 #include bool IsPrime(int n) { if (n m >> n; for (int i = m; i

문제설명 입출력 예제 개념 입력이 매우 클 때 소수를 찾는 문제다. 일반적인 O(N)의 시간 복잡도를 갖는 알고리즘은 시간 초과가 걸리기 때문에 효율적으로 소수를 구별해야 한다. 풀이 #include using namespace std; int main() { long long N, n; cin >> N; for (int i = 0; i > n; while (!isPrime(n)) n++; cout

문제설명 입출력 예제 개념 주어진 자연수 중 소수의 개수를 출력하는 문제다. 여기서 소수란 약수가 1과 자기 자신밖에 없는 수를 의미한다. 알고리즘 1부터 입력된 수까지 순회하며 나눠지는 수가 존재한다면 소수가 아니므로 break를 건 후 다음 반복으로 넘어가고, 나눠지는 수가 없다면 소수의 개수를 늘리는 식으로 접근하면 되는 간단한 문제다. 풀이 #include using namespace std; int N, cnt; int check; int main() { cin >> N; while (N--) { int num; check = 0; cin >> num; for (int i = 1; i < num; i++) { if (num % i == 0 && i != 1) break; check++; } if..