개발일지

문제설명 입출력 예제 개념 다양한 수를 처리하는 문제다. 산술 평균, 중앙값, 범위는 간단하게 해결할 수 있지만, 최빈값을 처리하는 과정이 까다롭고, 시간 초과에 자주 걸리므로 알고리즘 최적화를 잘해야 한다. 풀이 #include #include #include #include #include using namespace std; int main() { int N, sum = 0; cin >> N; vector v(N); unordered_map freq; 수의 개수 N, 산술 평균을 계산하기 위한 sum, 중앙값과 범위를 계산하기 위한 벡터 v, 최빈값을 계산하기 위한 해시맵 freq를 초기화한다. for (int i = 0; i > v[i]; sum += v[i]; fr..

문제설명 입출력 예제 개념 ChongChong과 만난 사람은 무지개 댄스를 추게 되므로, key로 아이디를 갖고 value로 무지개 댄스 여부를 확인할 수 있는 map 자료구조를 사용하면 쉽게 풀 수 있다. 즉, 문자열을 검사해 총총이를 만났으면 value값을 true로 바꾸면 된다. 풀이 #include #include using namespace std; int main() { int N, count = 0; cin >> N; map m; string str1, str2; 사람들이 만난 기록의 수 N, 무지개 댄스를 추는 사람의 수 count, 이러한 정보를 기록할 맵 자료구조 m, 사람들의 이름을 초기화할 문자열 str1, str2을 초기화한다. while (N--) { cin >> str1 >> ..

문제설명 입출력 예제 개념 엔터가 입력되고 난 후 들어온 사람의 숫자를 계산하는 문제다. enter가 입력되고 나서 중복되지 않은 사람의 수를 카운트하면 되므로, 자료구조 set을 이용하면 쉽게 풀 수 있다. 풀이 #include #include using namespace std; int main() { int N, count = 0; cin >> N; set m; string str; 채팅방의 기록 수 N, 곰곰티콘이 사용된 횟수 count, 집합 m, 유저 str을 초기화한다. while (N--) { cin >> str; if (str == "ENTER") { count += m.size(); m.clear(); continue; } m.insert(str); } count += m.size();..

문제설명 입출력 예제 개념 N번 째 창문이 열려 있으려면, 열고 닫은 횟수가 홀수번이어야 한다. 따라서 N의 약수의 개수가 홀수개여야 하고, 이런 특성을 만족하는 것은 제곱수다. 약수는 두 수가 짝을 이루어 곱해지므로 자연수의 약수의 개수는 짝수지만, 제곱수는 자기 자신을 곱하는 수가 추가되므로 홀수가 된다. 따라서 주어진 범위 내의 제곱수의 개수를 구하면 문제를 해결할 수 있다. 풀이 #include int main() { int N, count = 0; std::cin >> N; for(int i = 1; i * i

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