에라토스테네스의 채

1. 개요 안녕하세요. 오늘 풀이한 문제의 유형은 에라토스테네스의 채 응용문제입니다. 자연수를 소인수분해하는 작업은 모두 소수를 사용하여 진행이 됩니다. 소수를 계산하는 에라토스테네스의 채를 사용한다고 하여도 이를 사용해 자연수를 srqt(k)로 소인수분해를 진행해도 시간제한을 맞추기엔 어려워 보입니다.  핵심은 에라토스테네스의 채를 소수를 구하는 것으로 사용하는 게 아닌 나누어지는 가장 작은 수를 찾는 방법으로 응용이 필요했습니다. 2. 문제 풀이 앞서 설명한 것과 같이, 에라토스테네스의 채를 사용하여 5,000,000 이하의 임의의 자연수 k가 나누어지는 가장 작은 수를 찾아야 합니다. 해당 작업을 통해 sqrt(k) 이하의 수를 순회하면서 소인수를 찾는 로직을 생략할 수 있어 최적화가 가능해지고 T..

1. 문제 풀이 이번 문제는 에라토스테네스 채의 틀을 응용하여 최적화하는 문제였습니다. 처음부터 이 사실을 알고 진행한 것은 아니었고, 어떤 알고리즘을 적용할지 난해하여 시간복잡도를 개선하기위해 방법을 생각해놓고보니 에라토스였습니다. 임의의 카드를 하나 선택한 다음, 그 카드에 적힌 수의 배수를 탐색하면서 다른 플레이어의 카드 수가 존재한다면 승, 패를 확인할 수 있습니다. 이를 위해서 다른 플레이어의 카드의 수가 존재하는지를 판단하는 1'000'001 크기의 배열을 선언하였고, 있다면 그 플레이어의 인덱스 값을 저장해놓았습니다. [ 시간 복잡도 ] $$O( \sum_{i = 1}^{n}\frac{1000000}{card[i]} )$$ 입니다. 최악의 경우 n = 100'000이고, card[i] = i..

1. 문제 풀이 이번에 풀어본 문제는 백준 1016번 제곱 ㄴㄴ 수입니다. 문제의 유형은 에라토스테네스의 채 응용문제였습니다. 입력의 최대 1'000'000'000'000까지 들어올 수 있으나 범위가 최대 1'000'000으로 제한되어 있으므로 1,000,000 크기의 1차원 배열을 선언하여 풀 수 있습니다. 에라토스테네스의 채는 소수인 숫자들의 배수를 범위 내에서 모두 지워 결국 소수만 걸러지는 알고리즘입니다. 마찬가지로 2의 제곱수부터 모든 수의 제곱수의 배수를 제거해 주게 되면 문제를 풀이할 수 있습니다. 범위가 큰 숫자들을 다루는 만큼 오버플로우도 조심해야 되겠습니다. 2. 코드#include using namespace std;using ll = long long;ll mn, mx;vector ..