2026.02.24일차입니다.
왜 늦었냐면 번아웃 오고 방학이라 운동량이 없어서 그런가 건강도 안 좋아져서 늦었습니다.
약수, 배수와 소수 2 풀어보았습니다.
요약
- 유클리드 호제법,
<numeric>-gcd,lcm - 에라토스테네스의 체
- 지역변수의 스택
13241번 최소공배수
문제 링크
최소공배수를 구하는 단순한 문제입니다.
유클리드 호제법 이라는 알고리즘으로 최대공약수를 구한 뒤, 두 수의 곱을 최대공약수로 나누어 최소공배수를 구합니다.
유클리드 호제법
유클리드 호제법이란 최대공약수를 구하는 알고리즘입니다.
두 양의 정수 a, b(a > b)에 대해 a = bq + r (0 ≤ r < b)라고 하면
a, b의 최대공약수는 b, r의 최대공약수와 같다.
즉, gcd(a, b) = gcd(b, r) 이고
r = 0이라면 최대공약수는 b가 된다.
즉 gcd(a, b) = gcd(b, a % b)라는 뜻입니다.
a = bq + r, b의 공약수를 n이라고 가정해봅시다.
a = nx, b = ny로 가정할 수 있고, a = nyq + r이므로 r = n(x - yq)입니다.
따라서 r 또한 n으로 나누어 떨어집니다.
이로서 a, b의 모든 공약수가 b, r의 공약수가 될 수 있음을 알 수 있습니다.
이번에는 b, r = a - bq의 공약수를 m이라고 가정해봅시다.
b = mx, r = my로 가정할 수 있고 r = a - mxq이므로 a = m(xq + y)입니다.
따라서 a 또한 m으로 나누어 떨어집니다.
이로서 b, r의 모든 공약수가 a, b의 공약수가 될 수 있음을 알 수 있습니다.
두 증명을 합하여 봅시다.
a, b의 모든 공약수가 b, r의 공약수가 될 수 있고,
b, r의 모든 공약수가 a, b의 공약수가 될 수 있습니다.
이는 즉 필요충분조건으로 두 공약수의 집합이 완전히 일치함을 알 수 있습니다.
따라서 gcd(a, b) = gcd(b, r)은 일치합니다.
그런데 gcd의 결과는 왜 최대공약수일 수 있는 걸까요?
gcd(a, b)는 최종적으로 gcd(n, 0)이 됩니다.
모든 정수는 0을 나누어 떨어뜨리므로 n과 0의 최대공약수는 n 입니다.
따라서 유클리드 호제법을 통해 최대공약수를 구할 수 있습니다.
유클리드 호제법을 이용한 정답 코드는 아래와 같습니다.
#include <iostream>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int main() {
long long int a, b; cin >> a >> b; cout << a / gcd(a, b) * b;
}
해당 코드를 작성하며 배운 것은 두 가지 입니다.
gcd 함수
우리가 위에서 보았던 유클리드 호제법 gcd 함수의 조건은 a > b였습니다.
그런데 해당 코드에는 a > b인지 검사를 하지 않을 뿐더러 해당 문제의 예시 입력 대부분이 a < b입니다.
하지만 해당 코드는 정답 코드입니다.
gcd(a, b)가 대입되었고, 0 < a < b라고 가정해봅시다.
b != 0 이므로 gcd(b, a % b)가 반환됩니다.
이 때 a = b * 0 + a 이므로 a % b = a 입니다.
따라서 gcd(a, b) = gcd(b, a)가 됩니다.
a > b 검사를 할 필요 없이 a < b가 입력되면 나머지 연산자의 특성에 의해 gcd 함수 내에서 자동으로 두 값이 스왑 되는 것을 볼 수 있습니다.
long long int
최대 입력은 108은 약 21억 = 2 * 109까지 담을 수 있는 int형으로 충분히 담을 수 있는 크기입니다.
하지만 a * b를 진행할 경우 1016까지 커질 수 있고 이는 int형을 초과하므로 해당 문제는 long long int형을 사용하기를 권장합니다.
a * b / gcd(a, b)가 우리가 알고 있는 최소공배수를 구하는 식입니다.
하지만 해당 코드에서는 a / gcd(a, b) * b로 작성하였습니다.
두 식의 결과는 완전히 같지만 차이점은 중간 단계 a * b와 a / gcd(a, b)에서 있습니다.
만약 a, b가 매우 큰 수이고 int형일 때 이 둘을 먼저 곱하게 되면 int형의 범위를 초과하여 오버플로우가 발생할 수 있습니다.
하지만 나눗셈을 먼저 진행한다면 중간 계산값이 작게 유지되어 오버플로우를 방지할 수 있습니다.
이러한 방식을 사용했음에도 a, b를 int로 선언하면 오답입니다.
그 이유는 a, b가 매우 큰 수이면서 동시에 서로소일 수 있기 때문입니다.
해당 경우에는 위에서 설명한 오버플로우 방지 수법을 사용하여도 a / 1 * b가 되어 int를 초과하기 때문에 long long int를 사용해야 합니다.
그럼 오버플로우 방지를 안 써도 되는 게 아닌가? 하면
실제로 a * b / gcd(a, b) 또한 정답입니다.
a * b / gcd(a, b)의 최대이자 최악의 경우는 108 * 108 / 1은 1016입니다.
long long int의 범위는 약 263 즉, 약 1018으로 최악의 경우를 수용할 수 있습니다.
그냥 이런 식으로도 오버플로우를 방지할 수 있구나 하여 사용해보았습니다.
+ 추가
다시 복습을 하며 c++17부터 <numeric> 헤더에 gcd 함수, 심지어는 최소공배수를 구하는 함수인 lcm까지 내장되어 있다는 것을 알았습니다.
해당 코드는 다음과 같습니다.
#include <iostream>
#include <numeric>
using namespace std;
int main() {
long long int a, b; cin >> a >> b; cout << lcm(a, b);
}
이런 게 있었다니
1735번 분수 합
문제 링크
이번에도 유클리드 호제법을 이용한 문제입니다.
두 분수의 합을 기약 분수로 나타내는 간단한 문제로 분자와 분모를 최대공약수로 나누어 주면 되겠습니다.
아래는 정답 코드입니다.
#include <iostream>
using namespace std;
int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }
int main() {
int a, b, c, d, m, s, g; cin >> a >> b >> c >> d;
m = b * d; s = a * d + b * c; g = gcd(m, s); cout << s / g << ' ' << m / g;
}
이번에는 gcd 함수를 재귀 함수가 아닌 반복문으로 나타내어 보았습니다.
(a, b) = (b, a % b)로 갱신해나가다 b가 0이 되면 반복문을 종료하고 a를 반환합니다.
2485번 가로수
문제 링크
최대공약수 문제입니다.
여러 수의 최대공약수를 구하여 수들 간의 간격을 구하는 문제입니다.
아래는 정답 코드입니다.
#include <iostream>
using namespace std;
int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }
int main() {
int n; cin >> n; int* a = new int[n], * b = new int[n - 1]; for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n - 1; ++i) b[i] = a[i + 1] - a[i];
int temp = gcd(b[1], b[0]), r = 0; for (int i = 2; i < n - 1; ++i) temp = gcd(b[i], temp);
for (int i = 0; i < n - 1; ++i) r += (b[i] / temp - 1); cout << r;
}
배열 a는 가로수의 위치를 저장하고 배열 b는 가로수의 간격을 저장합니다.
배열 b를 통해 간격들의 최대공약수를 계산합니다.
계산된 최대공약수를 통해 각 가로수 사이에 들어갈 수 있는 가로수의 개수를 계산합니다.
다음과 같이 가로수 사이에 들어갈 수 있는 가로수의 개수는 b[i] / temp - 1이라는 것을 알 수 있습니다.
4134번 다음 소수
문제 링크
소수를 판별하는 간단한 문제입니다.
정답 코드입니다.
#include <iostream>
using namespace std;
bool is_prime(long long n) {
if (n == 2) return 1; else if (n == 1 || n %2==0) return 0;
for (long long i = 3; i * i <= n; i+=2) if (n % i == 0) return 0;
return 1;
}
int main() {
int t; cin >> t; while (t--) { long long n; cin >> n; while (is_prime(n)==0) ++n; cout << n<<'\n'; }
}
소수 판단은 브루트포스 방식으로 하나 하나 나누어가며 확인해야 합니다.
여기서 약수의 대칭성을 이용하면 테스트 케이스를 크게 줄일 수 있습니다.
약수의 대칭성에 대해서는 해당 글의 1978번 소수 찾기에서 설명해두었습니다.
또한 2일 경우에는 소수, 1 또는 짝수일 경우에는 소수가 아님을 미리 판단하여 테스트 케이스를 줄였습니다.
짝수일 경우를 제외하지 않고 2부터 판단하면 시간 초과로 오답 처리가 됩니다.
1929번 소수 구하기
문제 링크
두 수 사이에 존재하는 소수를 출력하는 문제입니다.
위 문제에서 사용한 방법 또는 에라토스테네스의 체를 이용하여 풀 수 있습니다.
소수 판정
정답 코드입니다.
#include <iostream>
using namespace std;
bool is_prime(int n) {
if (n == 2) return 1; else if (n == 1 || n % 2 == 0) return 0;
for (int i = 3; i * i <= n; i += 2) if (n % i == 0) return 0; return 1;
}
int main() {
int m, n; cin >> m >> n; for (int i = m; i <= n; ++i) if (is_prime(i)) cout << i << '\n';
}
위 문제에서 설명한 방법이므로 딱히 설명을 더 하진 않겠습니다.
에라토스테네스의 체
에라토스테네스의 체란 소수를 찾는 알고리즘으로 마치 체로 치듯 수를 걸러낸다고 하여 에라토스테네스의 체라고 합니다.
임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는 방법으로 한정된 구간이 매우 크지 않으면 매우 빠른 속도를 내는 알고리즘 입니다.
시간복잡도는 O(N log(log N))으로 O(N)에 근접한 효율을 보입니다.
- 1부터 자연수 n까지의 수의 배열을 만듭니다.
- 1은 소수가 아니므로 제거합니다.
- 2를 제외한 2의 배수를 모두 제거합니다.
- 3을 제외한 3의 배수를 모두 제거합니다.
- 4와 4의 배수는 2의 배수를 제거하며 모두 제거되었으므로 넘어갑니다.
- 5를 제외한 5의 배수를 모두 제거합니다.
- 해당 배열을 순회하며 제거되지 않았다면 해당 수를 제외한 해당 수의 배수를 모두 제거하고, 이미 제거되었다면 넘어갑니다.
- 끝까지 순회하였다면 최종적으로 배열에는 소수만 남아있게 됩니다.
정답 코드는 아래와 같습니다.
#include <iostream>
using namespace std;
int a[1000001] = { 0, 1 };
int main() {
int m, n;
for (int i = 2; i <= 1000001; ++i) for (int j = 2; i*j <= 1000001; ++j) a[i * j] = 1;
cin >> m >> n; for (int i = m; i <= n; ++i) if (!a[i]) cout << i << '\n';
}
에라토스테네스의 체를 진행하기 위해 배열을 생성합니다.
1,000,000까지 입력될 수 있으므로 +1 까지의 배열을 생성하고 이렇게 크기가 큰 배열은 전역으로 선언하여야 합니다.
지역 변수는 함수가 호출될 때 임시로 사용하는 스택 영역에 할당되어 크기가 매우 작게 제한되어 있기 때문입니다.
1을 먼저 제외한 뒤 에라토스테네스의 체를 진행합니다.
int a[] = {0, 1}
배열을 이렇게 선언한 이상 기본값은 0입니다.
따라서 소수라면 0, 소수가 아니라면 1을 저장할 것입니다.
2부터 임의의 수를 제외한 그 수의 배수를 모두 1로 저장합니다.
for (int i = 2; i <= 1000001; ++i) {
if (a[i]) continue;
for (int j = 2; i * j <= 1000001; ++j) a[i * j] = 1;
}
이렇게 작성할 경우 이미 삭제되었다고 판단된 수는 넘어갑니다.
해당 if문을 추가하면 더 빠르게 계산할 수 있습니다.
소수를 일일이 판단하는 첫 번째 코드의 성능은 메모리 2020 KB, 80 ms 입니다.
에라토스테네스의 체의 성능은 5928 KB, 40 ms로 속도는 위의 if문 추가를 통해 16 ms까지 향상시킬 수 있습니다.
에라토스테네스의 체는 미리 계산하여 배열에 저장해둬야 하기 때문에 더 많은 메모리를 소요합니다.
하지만 그 때 그 때 계산해야 하는 첫 번째 코드에 비해 에라토스테네스의 체는 미리 계산해둔 것을 꺼내오기 때문에 더 적은 시간이 소요됩니다.
17103번 골드바흐 파티션
문제 링크
에라토스테네스의 체로 소수를 모두 구한 뒤 합이 n인 한 쌍의 수가 모두 소수인지 확인하는 문제입니다.
아래는 정답 코드입니다.
#include <iostream>
using namespace std;
int a[1000001] = { 0, 1 };
int main() {
for (int i = 2; i < 1000001; ++i) for (int j = 2; i * j < 1000001; ++j) a[i * j] = 1;
int t; cin >> t; while (t--) {
int n, s = 0; cin >> n;
for (int i = 2; i <= n / 2; ++i) if (!a[i] && !a[n - i]) ++s; cout << s << '\n';
}
}
합은 한 쌍으로 이루어지므로 약수의 대칭성처럼 대칭성을 가집니다.
따라서 n/2까지만 판단하면 됩니다.
소수는 0, 소수가 아니면 1로 저장되어 있으므로 a[i], a[n - i]가 모두 0일 경우에만 출력하여야 합니다.
따라서 조건문은 다음과 같은데
!(a[i] || a[n - i])
이 조건과
!a[i] && !a[n - i]
이 조건 둘 다 드 모르간에 의해 같은 결과입니다.
하지만 후자는 !a[i]가 0인 경우, 소수가 아닌 경우 뒤까지 계산하지 않고 바로 끝내기 때문에 아래의 조건이 조금 더 낫습니다.
13909번 창문 닫기
문제 링크
창문이 닫혀있으면 열고 열려있으면 닫는 문제입니다.
6개의 창문이 있다고 가정해봅시다.
- 1 ~ 6 창문을 연다. (1, 1, 1, 1, 1, 1)
- 2의 배수 창문을 닫는다. (1, 0, 1, 0, 1, 0)
- 3의 배수 창문이 닫혀있으면 열고, 열려있으면 닫는다. (1, 0, 0, 0, 1, 1)
- 4의 배수 창문이 닫혀있으므로 연다. (1, 0, 0, 1, 1, 1)
- 5의 배수 창문을 닫는다. (1, 0, 0, 1, 0, 1)
- 6의 배수 창문이 닫혀있으므로 연다. (1, 0, 0, 1, 0, 0)
따라서 열려있는 창문의 개수는 2개입니다.
1의 배수는 모든 수이므로 첫 번째에서 모든 창문이 열리게 됩니다.
배수로서 한 번 더, 즉 두 번 등장하면 창문이 닫히고, 배수로서 세 번 등장하면 닫힌 창문이 다시 열립니다.
배수로서 네 번 등장하면 열린 창문이 다시 닫히고, 배수로서 다섯 번 등장하면 닫힌 창문이 다시 열립니다.
따라서 창문이 배수로서 홀수 번 등장한다면, 즉 약수가 홀수 개라면 창문이 최종적으로 열려 있게 됩니다.
약수의 개수가 홀수 개가 되기 위해서는 해당 수가 제곱수여야 합니다.
n이 제곱수라면 n의 제곱근이 자연수로 약수에 포함되어 약수가 홀수 개가 됩니다.
제곱수가 아니라면 n의 제곱근이 자연수가 아니게 되어 약수에 포함되지 않아 약수가 짝수 개가 됩니다.
따라서 해당 수 내에 존재하는 제곱수의 개수가 열려 있는 창문의 개수가 되고
이는 그 수의 제곱근의 정수 부분... 가우스 기호라고 볼 수 있겠습니다.
아래는 정답 코드입니다.
#include <iostream>
#include <cmath>
using namespace std;
int main() { int n; cin >> n; cout << (int)sqrt(n); }
Top comments (0)