알고리즘

[백준] 17427 약수의 합 2

✉️문제 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 📝 접근 10이하의 자연수 중에서 N의 배수를 몇 개인지 알아보자. (배수를 이용해서 약수를 구함) 1의 배수는 10 / 1 = 10개 2의 배수는 10 / 2 = 5개 (2, 4, 6, 8, 10) 3의 배수는 10 / 3 = 3개 (3, 6, 9) ... ... 10의 배수는 10 / 10 = 1개 g(n)의 값을 구하는 것이..

[백준] 1037 약수 (Java)

✉️문제 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 📝 접근 약수의 개수가 1과 자기자신을 빼고 주어진다. 따라서 주어진 약수 중에서 가장 작은 값과 가장 큰 값을 곱하면 된다. 🗝 문제풀이 package divisor; import java.util.Arrays; import java.util.Scanner; public class B1037R { public static void main(String[] args) { Scann..

[백준] 4375 1로만 이루어진 n의 배수(Java)

✉️문제 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 📝 접근 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력하면 된다. 이 때 1로만 이루어진 배수가 자료형의 범위를 넘어갈 수 있으므로, 혹은 더 효율적인 계싼을 위해서 나머지 연산을 이용한다. num = (num * 10) + 1; num = num % n; 🗝 문제풀이 import java.util.Scanner; public class B4375RRR { public static void main(String[] args) { Sc..

[백준] 10430 나머지 (Java)

✉️문제 https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 📝 접근 컴퓨터의 정수는 저장할 수 있는 범위가 지정되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하는 문제가 등장한다. 이 때 다음과 같은 성질을 이용해서 int또는 long과 같은 자료형의 범위로 제한해주어야 한다. (A + B) mod M = (( A mod M ) + ( B mod M )) mod M (A x B) mod M = (( A mod M) x ( B mod M )) mod M (A - B ) mod M = (( A mod M) - (B mod M) mod M 🗝 문제풀이 위..

[알고리즘] 최대 공약수, 최소공배수

최대 공약수를 구하는 알고리즘 중 가장 유명한 유클리드 호제법에 대해 알아보자. 유클리드 호제법 a를 b로 나눈 나머지를 r이라고 할 때, GCD(a, b) = GCD(b, r)이다. r이 0일 때의 b가 최대 공약수이다. 위의 정의를 GCD(24, 16)을 통해 알아보자. 1. 24(a)를 16(b)로 나눈다. 24 % 16 = 8(r) 2. 16(b)를 8(r)로 나눈다. 3. 8(b)와 0(r)을 계산해야 하는데 r = 0이므로 이 때의 b값인 8인 최대 공약수가 된다. int gcd(int a, int b) { while ( b != 0) { int r = a % b; a = b; b = r; } return a; } 최소공배수 최소공배수는 LCM이라고 하며 GCD를 응용해서 구할 수 있다. 최소..