약수 구하기의 시간복잡도
N의 약수를 모두 구하는 시간복잡도는 O(√N)이다.
1부터 sqrt(N)까지 모든 자연수로 나누기 때문.
1037번_약수
📌문제
양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.
ex_ A = 24일 때 진짜 약수 A는 2,3,4,6,8,12
✍입력
첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.
📄출력
첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.
👀예제
입력
2
4 2
출력
8
⏳시간복잡도
약수의 최소값과 최대값을 구해서 곱하면 정답
n의 진짜 약수의 개수가 M개이면 시간복잡도는 O(M)
🌴 Code
package math;
import java.util.Scanner;
public class no1037_약수 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int [] num = new int[count];
for (int i=0;i<count;i++){
num[i] = sc.nextInt();
}
int max = num[0];
int min = num[0];
for (int i=1;i<count;i++){
max = Math.max(max,num[i]);
min = Math.min(min,num[i]);
}
System.out.println(max*min);
}
}
17427_약수의합2
📌문제
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다.
예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다.
자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다.
x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
시간제한 0.5초
✍입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
📄출력
첫째 줄에 g(N)를 출력한다.
👀예제
| 입력 | 출력 |
|---|---|
| 1 | 1 |
| 2 | 4 |
| 10 | 87 |
| 70 | 4065 |
| 10000 | 82256014 |
⏳시간복잡도
f(A)의 시간복잡도 O(√A)
g(N) = N x O(√N) = O(N√N)
N의 범위는 (1 ≤ N ≤ 1,000,000)
N√N ≤ 1,000,000 x 1000 = 10억 = 10초..
시간제한이 0.5초이기 때문에 위의 풀이로는 x
⭐약수의 반대는 배수다라는 아이디어로 풀것
N이하의 자연수 중에서 1의 배수의 개수(1을 약수로 갖는 수)는 N/1개
N이하의 자연수 중에서 2의 배수의 개수(2을 약수로 갖는 수)는 N/2개
N이하의 자연수 중에서 3의 배수의 개수(3을 약수로 갖는 수)는 N/3개
...
N이하의 자연수 중에서 i의 배수의 개수(i을 약수로 갖는 수)는 N/i개
시간복잡도 O(1) X N = O(N)
🌴 Code
package math.no17427약수의합2;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
long g = 0; // ❗ 데이터타입 주의 int는 약 21억까지만 가능
for (int i=1;i<=a;i++) g += a/i * i;
System.out.println(g);
}
}
17425_약수의합
📌문제
위의 약수의 합2 랑 같은 문제이지만 테스트 케이스가 추가됨.
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다.
예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다.
자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다.
x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
시간제한 1초
✍입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
📄출력
각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.
👀예제
| 입력 | 출력 |
|---|---|
| 5 1 2 10 70 10000 | 1 4 87 4065 82256014 |
❓ 문제 풀이
g(N) = O(N)
O(TN) = 100,000,000,000(천억) 이므로 시간제한 1초 (1억) 보다 크므로 초과.
💡 테스트 케이스 문제를 풀 때 주의할점
ex_ N이 100이거나 1000이여도 24의 약수를 구해야한다. 이는 입력에 영향을 받지 않고 일정한 값을 가진다는 것을 알 수 있다. 변하지 않는 일정한 값을 매번 구하는 것은 비효율적!
한번만 구해두고 재활용..테스트 케이스마다 구하지 않고 한번에 구해둔 다음에 다시 이용
앞의 문제에서 사용했던 "약수는 배수의 반대"의 아이디어를 이용하여 약수들의 합을 미리 다 구해둔다.
🌴 Code
Scanner와 System.out.print 써도 시간초과..
package math.n17425_약수의합;
import java.io.*;
public class Main {
static final int MAX = 1000000;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long [] data = new long [MAX+1];
//모든 수가 1을 약수로 가짐
for (int i=1;i<=MAX;i++) data[i] = 1;
//⏳ O(NlogN) ❗ ❗ ❗
for (int i=2;i<=MAX;i++){ //i를 약수로 가지면 data에 넣어주기
for (int j=1; i*j<=MAX;j++) {
data[i*j] += i; //index는 약수를 가지는 수를 의미
}
}
//⏳ O(N)
long [] g = new long[MAX+1];
for (int i=1;i<=MAX;i++){
g[i] = g[i-1] + data[i]; // ❗ 배열 초기화 디폴트 값은 0
}
/********************여기까지가 미리 한번에 구해둔 것 **********************/
//⏳ O(T)
int t = Integer.parseInt(bf.readLine()); // readLine 메소드는 String 값만 받을 수 있다.
while (t-- >0){
int n = Integer.parseInt(bf.readLine());
bw.write(g[n]+"\n");// ❗ write는 아스키 코드에 따른 char형 값이 출력된다.
// 그러나 i와 개행 처리 문자열 "\n" 을 더하면 String 으로 자동 형변환 되기 때문에
// 저장되어 있는 int 값 그대로 출력이 가능하다. "\n" 안하면 에러생겼어서 당황했었음
}
bw.flush();
bw.close(); // ❗ 꼭꼭 close 해주어야 함
//⏳ 총 시간 복잡도 O(NlogN+N+T) = O(NlogN+T)
}
}⏳ 시간 복잡도
배열에 자연수 A의 약수들의 합을 넣고 index는 자연수 A.
data[A] = f(A)
시간 복잡도 : O(N x ??)
- data의 시간 복잡도
i=2, j= 1~N/2 -> N/2
i=3, j= 1~N/3 -> N/3
...
i=N, j= 1~N/N -> N/N
=> N/2 + N/3 ...+ N/(N-1) + N/N
=> O(NlogN)
🔔 1+1/2+1/3 ... +1/N≤ logN+1
⏳ 최종 O(NlogN+T)
= 6,000,000 + 100,000 = 610만 ＜ 1억 이므로 시간제한 만족함.
