오늘의 학습 키워드
</> 완전 탐색
공부한 내용 본인의 언어로 정리하기
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int[] results = new int[T];
for(int t = 0; t < T; t++){
int n = sc.nextInt();
int m = sc.nextInt();
int count = 0;
for(int a = 1; a < n; a++){
for(int b = a+1; b < n; b++){
if(((a*a)+(b*b)+m)%(a*b) == 0){
count++;
}
}
}
results[t] = count;
}
for (int result : results) {
System.out.println(result);
}
}
}오늘의 회고
오늘 문제는 두 정수 n과 m이 주어졌을 때, 0 < a < b < n인 정수 쌍 (a, b) 중에서 (a^2+b^2+m)/(ab)가 정수인 쌍의 개수를 구하는 프로그램을 작성하는 것이다.
비슷한 공식으로는 유클리드 알고리즘과 관련된 식 또는 정수론에서 다루는 다양한 함수들이 있다고 한다.
예시로는 (a^2+b^2+2ab)/(ab)가 있는데 비교를 해보았을때 m이2ab라는 차이밖에 없어서 조금 더 알아보았다.
m이 2ab가 되어 (a+b)^2가 되는데 이 식이 항상 정수인 경우는 a와 b가 서로 나누어 떨어질 때, 즉 a가 b의 배수이거나 b가 a의 배수일 때이다.
따라서 m = 2ab일 때, 정수가 되려면 a와 b가 서로 같은 값이거나, a와 b가 서로 나누어 떨어지는 관계가 되어야한다.
하지만 문제에서 주어진 조건은 a가 b보다 작다는 조건이 있었으므로 b를 a로 나누었을 때 나머지가 0이 된다는 것이다. 그리고 a 와 b는 n보다 작다는 조건도 만족해야한다.
이 조건을 만족하기 위해서는 a는 1부터 b는 a+1부터 탐색을 시작하면 모든 값이 만족이 된다.
그리고 진행 조건으로는 a와 b가 둘다 n보다 작을 때 진행을 시켜주면 되겠다.
공식의 결과값이 정수인지 확인하려면 나누고 난 후 나머지가 0이 되면 정수가 되는데 이때는 나누기 대신 %로 나머지가 0인지 확인해주면 되겠다. 그리고 조건이 만족된다면 출력해줄 개수를 추가해주면 되겠다.
앞서 실버2 수준의 문제를 풀다가 어제 오늘 브론즈 수준의 문제로 내려왔더니 확실히 푸는 것이 수월해졌다. 여기서 자료구조의 이해의 중요성을 한번 더 느낀것 같다.
AI 코드리뷰
현재 코드의 장점
- 문제를 정확하게 해결하고 있습니다.
- 입력을 적절히 처리하고 결과를 배열에 저장한 후 출력하고 있습니다.
- 코드 구조가 명확하고 이해하기 쉽습니다.
현재 코드의 단점
- 중첩된 반복문으로 인해 시간 복잡도가 높습니다.
- 큰 입력값에 대해 비효율적일 수 있습니다.
- 모듈러 연산을 반복적으로 수행하여 불필요한 계산이 발생할 수 있습니다.
시간 복잡도
- 현재 코드의 시간 복잡도는 O(T * n^2) 입니다. 여기서
T는 테스트 케이스의 수이고,n은 각 테스트 케이스의 입력값입니다. 중첩된 두 개의for루프로 인해n^2의 복잡도가 발생합니다.
개선된 코드 제안
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int[] results = new int[T];
for(int t = 0; t < T; t++){
int n = sc.nextInt();
int m = sc.nextInt();
int count = 0;
for(int a = 1; a < n; a++){
int target = a * a + m;
int left = a + 1, right = n - 1;
while(left <= right){
int mid = left + (right - left) / 2;
long product = (long)a * mid;
if(target % product == 0){
count += (right - mid + 1);
left = mid + 1;
} else if (target < product) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
results[t] = count;
}
for (int result : results) {
System.out.println(result);
}
}
}현재 코드의 장점
- 시간 복잡도가 크게 개선되었습니다.
- 이진 탐색을 사용하여 효율성이 향상되었습니다.
- 큰 입력값에 대해서도 빠르게 동작할 수 있습니다.
현재 코드의 단점
- 코드가 약간 더 복잡해져 이해하기 어려울 수 있습니다.
- 이진 탐색 구현에 주의가 필요합니다 (예: 오버플로우 방지).
시간 복잡도
- 개선된 코드의 시간 복잡도는 O(T n log n)입니다. 외부 루프는
n번 반복하고, 각 반복에서 이진 탐색(log n)을 수행하므로 전체적으로 n * log n의 복잡도를 가집니다.
개선 사항 설명
- 이진 탐색 도입:
b에 대한 반복문을 이진 탐색으로 대체하여 시간 복잡도를 O(n)에서 O(log n)으로 줄였습니다. - 수학적 최적화:
(aa + bb + m) % (ab) == 0조건을 변형하여(aa + m) % (ab) == 0으로 단순화했습니다. 이를 통해bb항을 제거하고 계산을 줄였습니다. - 오버플로우 방지:
long타입을 사용하여 큰 숫자의 곱셈에서 발생할 수 있는 오버플로우를 방지했습니다.
이 개선된 버전은 원래 코드의 정확성을 유지하면서 성능을 크게 향상시켰습니다. 특히 큰 입력값에 대해 매우 효율적으로 동작할 것입니다.
내일 공부할 것 :
이진탐색을 사용해 개선한 코드에 대해서 복습해보아야겠다.
문제
