개발일지

문제설명 입출력 예제 개념 주어진 정수 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

문제설명 입출력 예제 개념 심어져 있는 N개의 가로수 사이에 간격이 일정하도록 심어야 하는 가로수의 개수를 구하는 문제다. 이 문제를 해결하기 위해서 가로수들 사이의 거리를 구한 후, 거리를 일정하게 만들기 위해 최대 공약수 개념을 사용해야 한다. 풀이 #include #include #include int main() { int N; std::cin >> N; std::vector v(N); std::vector dist(N-1); for (int i = 0; i > v[i]; for (int i = 1; i < v.size(); i++) dist[i - 1] = v[i] - v[i - 1]; 가로수의 개수 N을 초기화하고, 가로수가 놓여 있는 위치를 초기화할 벡터 ..

문제설명 입출력 예제 개념 기약분수는 분자와 분모를 더 이상 나눌 수 없는 분수를 의미한다. 따라서 분자와 분모를 통분한 후, 최대 공약수를 나눠주면 답을 찾을 수 있다. 풀이 #include #include int main() { int n1, d1; std::cin >> n1 >> d1; int n2, d2; std::cin >> n2 >> d2; int n = n1 * d2 + n2 * d1; int d = d1 * d2; int gcd = std::gcd(n, d); std::cout

문제설명 입출력 예제 개념 최소 공배수를 찾는 문제다. 입력 A와 B에 대하여 두 수의 최소 공약수를 구하고, A * B / 최소 공약수를 하면 최대 공배수를 구할 수 있다. (유클리드 호제법) 풀이 #include int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } int main() { long long int A, B, gcd; std::cin >> A >> B; gcd = GCD(A, B); std::cout

문제설명 입출력 예제 개념 문자열 S에 대해 서로 다른 부분 문자열의 개수를 구하는 문제다. 여기서 연속된 일부분이라는 것에 주목해야 한다. 즉, S의 길이가 1인 부분 문자열은 a, b, a, b, c가 되고, 여기서 서로 다른 부분 문자열은 a, b, c S의 길이가 2인 부분 문자열은 ab, ba, ab, bc가 되고, 여기서 서로 다른 부분 문자열은 ab, ba, bc S의 길이가 3인 부분 문자열은 aba, bab, abc가 되고, 여기서 서로 다른 부분 문자열은 aba, bab, abc S의 길이가 4인 부분 문자열은 abab, babc가 되고, 여기서 서로 다른 부분 문자열은 abab, babc S의 길이가 5인 부분 문자열은 ababc가 되고, 여기서 서로 다른 부분 문자열은 ababc 따..

문제설명 입출력 예제 개념 집합 A와 B가 주어졌을 때 (A - B) ∪ (B - A)의 값을 구하는 문제다. 자료구조 map을 이용해서 푸는 방법도 있지만, 필자는 조금 다르게 풀었다. 두 집합의 원소를 벡터에 삽입 교집합을 이진 탐색을 이용하여 정수형 변수에 삽입 벡터의 크기에서 교집합의 원소의 차를 출력 풀이 #include #include #include int main() { int N, M, n, count = 0; std::cin >> N >> M; std::vector v(N + M); 집합 A, B의 원소의 개수 N, M, 입력받을 숫자 n, 교집합의 수 count를 초기화해준다. 그리고 N + M의 크기를 가지는 벡터 v를 초기화해 준다. for (int i = 0; i < N; i++..

문제설명 입출력 예제 개념 N개의 문자열과 M개의 문자열 중 겹치는 문자열을 출력하는 문제다. 여기서 사전순으로 출력해야 하기 때문에 set 자료 구조를 이용하여 저장과 동시에 정렬을 하면 편하게 해결할 수 있다. 풀이 #include #include #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; std::string str; std::vector v; std::set res; 문자열의 수 N, M, 입력받을 문자열 str, 초기에 N개의 벡터를 저장할 벡터 v, 최종 적으로 자료를 담을 res를 초기화한다. std::cin >> N >> M; while (N--) { std:..