본문 바로가기

Algorithm

Baekjoon 3908 서로 다른 소수의 합 2019. 11. 11. Link https://www.acmicpc.net/problem/3908 결과 2052 KB / 0 ms 언어 C++ 17 풀이 에라토스테네스의 체를 이용해 소수를 먼저 구한다. [선택된 개수][1120보다 죽은 수]를 저장하는 O(kn) DP를 구한다. 입력되는 값에 대하셔 해당 위치의 값을 출력한다. 소스코드 #include #include using namespace std; vector primes; const short MAX = 1120; const short PRIME_MAX = 187; const short SELECT_MAX = 14; int prime_dp[SELECT_MAX + 1][MAX + 1]; void find_prime() { bool prime[MAX + 1] = { tr..
Baekjoon 3896 소수 사이 수열 2019. 11. 11. Link https://www.acmicpc.net/problem/3896 결과 4152 KB / 24 ms 언어 C++17 풀이 최대 값이 1299709로 충분히 배열로 만들만 하다 입력값을 기준으로 조건을 걸어서 소수라면 0을 합성수라면 1 ~ 합성수까지의 개수를 구하면 된다. 매번 결과를 구해도 될만큼 테스트 케이스가 많지 않기 때문에 매 순간 돌려도 된다. 해당 수가 소수인지 아닌지를 판별하는 방법은 에라토스테네스 체를 구하는 과정의 배열을 재 사용하도록 한다. 소스코드 #include #include using namespace std; const int MAX = 1299709; bool prime[MAX + 1] = { true, true }; vector primes; void eratos..
Baekjoon 2512 예산 2019. 11. 11. Link https://www.acmicpc.net/problem/2512 결과 2148 KB / 0 ms 출처 BOJ 언어 C++ 17 풀이 이분탐색에 기반한 문제 풀이 0 ~ 최대값 사이에서 이분탐색을 진행하며 조건에 맞는 값을 계산한다. 입력된 총 예산을 기준으로 범위를 수정해가며 이분탐색이 종료될까지 진행한다. 소스코드 #include #include using namespace std; int getMax(vector inputs) { int res = 0; for (int i = 0; i < inputs.size(); i++) if (res < inputs[i]) res = inputs[i]; return res; } int getSum (vector inputs, int mxm) { int ..
Baekjoon 1929 소수 구하기 2019. 8. 23. Link https://www.acmicpc.net/problem/1929 소스결과 2884 KB / 16 ms 출처 Baekjoon 언어 C++ 17 분류 에라토스테네스의 체 설명 입력된 범위 내에 있는 소수를 전부 출력하자 최대 범위가 100만이다. 시작 값이 소수인지를 확인하면 절대 시간내에 해결이 안된다. 에라토스테네스의 체를 이용해 100만까지 구한 후 소수를 따로 저장하면 된다. 알고리즘 1. 에라토스테네스의 체를 이용해 소수만 저장한다. 2. 저장된 소수를 처음부터 탐색한다. 3. 범위 내에 들어가면 출력하고 범위를 벗어나면 출력을 종료한다. 소스코드 #include using namespace std; const int MAX = 1000000; void eratos(bool arr[MAX..
Baekjoon 2870 수학숙제 2019. 8. 23. Link https://www.acmicpc.net/problem/2870 소스결과 2128 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 문자열 처리, 정렬 설명 문자와 숫자가 섞여있는 문자열에서 숫자만 뽑아 오름차순으로 출력하자. 문자열 파싱할 때 자주 볼법한 문제 굳이 숫자로 안바꿔도 문제가 없다. 파싱 알고리즘만 잘짜면 쉬운 문제다. 소스코드 #include #include #include #include using namespace std; string converting(string& str) { string res; if (str.length() == 1) res = str; else { int zeroCounting = 0; while (str[zeroCounting] ==..
Baekjoon 1431 시리얼 번호 2019. 8. 23. Link https://www.acmicpc.net/problem/1431 소스결과 1996 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 정렬 소스코드 #include #include #include #include using namespace std; bool cmp(string& str1, string& str2) { int len1 = str1.length(); int len2 = str2.length(); if (len1 != len2) return len1 < len2; int str1Sum = 0; int str2Sum = 0; for (int i = 0; i < len1; i++) { if ('0' inputs[i]; sort(inputs.begin(), inputs.end..
Baekjoon 1644 소수의 연속합 2019. 8. 23. Link https://www.acmicpc.net/problem/1644 소스결과 8972 KB / 32 ms 출처 BOJ 언어 C++ 17 분류 에라토스테네스의 체, 투 포인터 설명 특정 값을 연속된 소수의 합으로 나타내자 소수를 구하는 것도 문제, 어떻게 연속합을 구하는지도 문제 소수는 에라토스테네스의 체로 구하면 상당히 빠른 시간 내에 구해진다. 다만 연속합에 대해서 투 포인터 알고리즘을 모른다면 해결이 불가능한 문제가 된다. prefixSum으로 어찌어찌 비벼볼 수 있겠다는 생각이 들긴 하지만! 최대 범위가 400만이기 때문에 거의 불가능에 가깝다. 따라서 피벗을 이용한 투 포인터 알고리즘을 사용하자. 알고리즘 1. 에라토스테네스의 체를 이용하여 소수를 구한다. 2. 투포인터 알고리즘을 이용하여..
Baekjoon 10814 나이순 정렬 2019. 8. 23. Link https://www.acmicpc.net/problem/10814 소스결과 9820 KB / 84 ms 출처 Baekjoon 언어 C++ 17 분류 정렬 설명 나이순으로 정렬하자! 단 입력 순서가 지켜져야 하므로 stable한 sort를 구현하거나 사용해야 한다. 소스코드 #include #include #include #include using namespace std; struct Contact { int age; string name; bool operatorage > contacts[i].age >> ..

티스토리툴바