꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1327 BFS(Breadth First Search) 알고리즘 문제였습니다.문자열의 substr 메소드를 잘 이용하면 쉽게 풀 수 있는 문제였습니다.visited는 map을 이용하여 공간 복잡도를 줄이도록 노력했습니다. #include #include #include #include #include using namespace std; int N, K; int BFS(string s) { queue q; q.push({ s, 0 }); map visited; string target = s; sort(target.begin(), target.end()); //오름차순 while (!q.empty()) { string cur = ..

문제 링크입니다: https://www.acmicpc.net/problem/1648 현재 확인하는 칸이 앞으로 확인할 칸들 중 좌측상단에 있다고 가정하고 풀어야하는 문제였습니다.백준님의 슬라이드쉐어(https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648)를 참고하여 풀었고 이런 풀이를 생각해본 적이 없어서 놀라웠습니다. 알고리즘은 아래와 같습니다.1. 좌측상단부터 우측하단까지 순서대로 칸마다 숫자를 부여합니다.2. board번째 칸부터 M개의 칸들을 비트마스킹을 이용하여 확인합니다.i) 해당 칸이 칠해져있다면 다음 칸을 좌측상단으로 기준으로 하고 확인합니다.ii) 해당 칸이 칠해져있지 않다면 2*1 격자를 채워줍니다.a) 만약 오른쪽에도 배치할 수..

문제 링크입니다: https://www.acmicpc.net/problem/9421 에라토스테네스의 체를 이용해 쉽게 풀 수 있는 문제였습니다.소수를 모두 구하고 N 이하인 숫자에 대해 소수상근수인지 func 함수를 통해 판별하면 되는 문제였습니다. #include #include #include using namespace std; const int MAX = 1000000 + 1; int minFactor[MAX]; vector prime; void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for (int i = 2; i < MAX; i++) minFactor[i] = i; for (int i = 2; i*i < MAX; i++) if (min..

문제 링크입니다: https://www.acmicpc.net/problem/11653 에라토스테네스의 체를 이용해 쉽게 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 10000000 + 1; int minFactor[MAX]; vector prime; void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for (int i = 2; i < MAX; i++) minFactor[i] = i; for (int i = 2; i*i < MAX; i++) if (minFactor[i] == i) for (int j = i * i; j < MAX; j += i) if (minFactor..

문제 링크입니다: https://www.acmicpc.net/problem/1124 에라토스테네스의 체를 이용하여 간단히 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 100000 + 1; int minFactor[MAX]; vector prime; void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for (int i = 2; i < MAX; i++) minFactor[i] = i; for (int i = 2; i*i < MAX; i++) if (minFactor[i] == i) for (int j = i * i; j < MAX; j += i) if (minFactor[..

문제 링크입니다: https://www.acmicpc.net/problem/2312 에라토스테네스의 체를 이용하면 쉽게 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 100000 + 1; int minFactor[MAX]; vector prime; void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for (int i = 2; i < MAX; i++) minFactor[i] = i; for (int i = 2; i*i < MAX; i++) if (minFactor[i] == i) for (int j = i * i; j < MAX; j += i) if (minFactor[j..

문제 링크입니다: https://www.acmicpc.net/problem/2904 에라토스테네스의 체를 이용하여 푸는 재밌는 문제였습니다. 알고리즘은 아래와 같습니다.1. 우선 에라토스테네스의 체를 이용해 소수를 모두 구합니다.2. 이 후 입력받는 숫자들마다 소인수 분해를 진행하는데 해당 숫자에서 사용하는 소수의 개수와 모든 숫자에 대해 사용되는 소수의 개수를 모두 업데이트해줍니다.3. 최대 공약수의 일부가 되기 위해서는 해당 소수가 N으로 나누었을 때 1 이상이여야합니다.i) 조건이 성립한다면 해당 소수 * (N으로 나누었을 때 몫)만큼을 최대공약수에 곱해줍니다.ii) 그리고 N개의 숫자 중 해당 소수의 개수가 부족한 숫자가 해당 소수가 많은 숫자로부터 소수를 받아옵니다.4. 3번을 진행한 뒤 i)에..

문제 링크입니다: https://www.acmicpc.net/problem/1456 long long 범위 때문에 정말 많이 틀렸던 문제였습니다.에라토스테네스의 체를 이용해 소수를 구하고 해당 수의 N 승이 A 이상 B 이하인지를 확인하는데$$10^7 * 10^{14} = 10^{21}은\;long\;long의\;범위를\; 초과하므로\; if(prime[i]> A >> B; eratosthenes(); long long result = 0; for (int i = 0; i < prime.size(); i++) { long long num = prime[i]; //num이 long long 범위 초과하지 않도록 하는 조건 while (prime[i] = A) result++; num *= prime[i];..

문제 링크입니다: https://www.acmicpc.net/problem/3896 에라토스테네스의 체를 이용하여 푸는 문제였습니다. 주의할 점은 소수 사이 수열의 길이는 (소수들의 개수 + 1)이라는 것입니다. #include #include using namespace std; const int MAX = 1299709 + 1; int minFactor[MAX]; void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for (int i = 2; i < MAX; i++) minFactor[i] = i; for (int i = 2; i*i < MAX; i++) if (minFactor[i] == i) for (int j = i * i; j < MAX;..

문제 링크입니다: https://www.acmicpc.net/problem/16563 에라토스테네스의 체를 이용하면 쉽게 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 5000000 + 1; int minFactor[MAX]; vector prime; vector result; void eratosthenes(void) { minFactor[0] = minFactor[1] = -1; for (int i = 2; i < MAX; i++) minFactor[i] = i; for (int i = 2; i*i < MAX; i++) if (minFactor[i] == i) for (int j = i * i; j < MAX; j += i..