자연수를 더해서 최소공배수를 최소로 만들기

1. 문제 11414번: LCM (acmicpc.net) 11414번: LCM 두 자연수 A, B가 주어졌을 때, A + N과 B + N의 최소공배수가 최소가 되는 자연수 N을 구하시오. www.acmicpc.net 2. 풀이 임의의 정수 k에 대하여 $$gcd(a,b) = gcd(a+kb,b)$$ 를 이용하자. 그러면, $$gcd(a+n, b+n) = gcd(a-b, b+n) = gcd(a+n, b-a)$$ 를 얻는다. 그래서 a < b이면, $a+n \leq gcd(a+n,b+n) \leq b-a$ 최대공약수로 gcd(a+n,b+n) = gcd(a-b,b+n) = gcd(b-a,b+n) = b-a라고 한다면... (gcd(a,b) = gcd(abs(a),abs(b))이기 때문) b+n이 b-a의 배수라는..

• format_list_bulleted 정수론
• · 2023. 6. 17.
• textsms

harmonic lemma 응용하기 - 올림으로 된 조화수열 합을 빠르게 구하는 방법

1. 문제 15897번: 잘못 구현한 에라토스테네스의 체 (acmicpc.net) 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 2. 풀이 다음에서 6번줄이 몇번이나 실행되는지 구하는 문제 int n; cin >> n; int* sieve = new int[n+1]; for (int i = 1; i

• format_list_bulleted 정수론
• · 2023. 6. 17.
• textsms

1부터 n까지 모든 자연수들 각각의 약수의 누적합을 구하는 방법들(double counting, harmonic lemma, dynamic programming)

1. 문제 2247번: 실질적 약수 (acmicpc.net) 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1부터 n까지 각각 약수들 중 1과 자기 자신을 제외한 약수들의 합들의 누적합을 구하는 문제 2. 방법1 가장 쉬운 방법은 1부터 n까지 순회해서 각 자연수를 i라고 한 다음, i에 대한 모든 약수를 구해서 1과 자기 자신을 제외하고 더하면 된다 약수는 $O(\sqrt{n})$ 알고리즘으로 모두 나눠보는 방식으로 구한다 그런데 p = 1부터 시작하면, i를 1로 나누면 1과 i를 더하게 되는데 실질적 약수라면 1과 i를 제외한 나머지들의 합을 구해야하니 p = 2부터 시작하는게 핵심 n = int(input()) ans..

• format_list_bulleted 정수론
• · 2023. 6. 15.
• textsms

그리디 알고리즘 - 효과적으로 겹치는 구간을 하나로 합치는 방법(스위핑 기본)

1. 문제 2170번: 선 긋기 (acmicpc.net) 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 2. 풀이 x와 y 사이 선을 긋는데, 총 얼마만큼 선을 그었는지 구하는 문제 한번 그어진 곳을 또 긋는다고 해서, 중복해서 세지 않는다 어려워보여도 예제를 보고 머릿속으로 생각해보면 생각보다 문제가 간단하다 4 1 3 2 5 3 5 6 7 수직선 위에 1,3을 찍고 그어본다. 그러면 그은 길이가 2인데 이제 2,5를 찍고 그어본다 그러면 총 그은 길이는 4임을 알 수 있는..

• format_list_bulleted 그리디 알고리즘
• · 2023. 6. 9.
• textsms

투 포인터로 원소를 삭제하면서 가장 긴 수열을 찾을 수 있을까?

1. 문제 22862번: 가장 긴 짝수 연속한 부분 수열 (large) (acmicpc.net) 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 2. 풀이 투 포인터로는 원소를 포함시키면서 가장 긴 수열을 찾아가는 건데 어떻게 해야 최대 K번 원소를 삭제하면서 가장 긴 짝수만 포함된 연속 부분 수열을 찾을 수 있을까? 생각보다 간단하다 투 포인터 i,j로 범위를 확장해나가는데, j번 원소가 홀수라면, K값을 감소시키고 길이를 증가시키지 않는다. K가 홀수를 포함시킬 수 있는 최대 기회라고 생각한다면, 원소를 실제로 삭제하지 않고도 마치 삭제한..

• format_list_bulleted 투 포인터 알고리즘
• · 2023. 6. 8.
• textsms

정수 M으로 나누어 떨어지는 부분 구간합을 선형시간에 구하는 놀라운 방법

1. 문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 2. 풀이 누적합이야 prefix sum 방법으로 O(N)에 미리 구해놓고 [i,j]의 구간합은 O(1)에 구할 수 있는데 정수 M으로 나누어 떨어지는 구간합 [i,j]를 어떻게 하면 아주 빠르게 구할 수 있을까 가장 쉬운 방법은 모든 i,j에 대해 검사하는 이중 for문 방법이지만 N이 $10^{6}$이다 보니 $O(N^{2})$으로는 1초안에 통과할 수..

• format_list_bulleted 누적 합 알고리즘
• · 2023. 6. 6.
• textsms