문제 이해하기
숫자 n을 입력받아, 다음 디오판틴 방정식(Diophantine equation)을 만족하는 모든 정수 쌍 x와 y를 찾는 JavaScript 함수를 작성해야 합니다.
x² − 4y² = n
함수는 조건을 만족하는 모든 [x, y] 쌍을 배열 형태로 반환해야 합니다.
접근 방법
이 방정식은 인수분해 공식을 활용하면 효율적으로 풀 수 있습니다. 좌변을 인수분해하면 다음과 같습니다.
(x − 2y)(x + 2y) = n
여기서 a = x − 2y, b = x + 2y라고 하면 a × b = n이 되므로, n의 약수 쌍 (a, b)를 구한 뒤 아래 식으로 x와 y를 역산할 수 있습니다.
x = (a + b) / 2
y = (b − a) / 4
따라서 1부터 √n까지의 범위에서 n을 나누어 떨어지게 하는 약수 a를 찾고, b = n/a를 계산한 후, 위 두 식의 결과가 모두 정수일 때만 답에 포함시키면 됩니다. 이 방법은 완전 탐색보다 훨씬 적은 연산으로 모든 해를 구할 수 있습니다.
예제 코드
다음은 위 로직을 구현한 코드입니다.
const num = 90005;
const findSolution = (num = 1) => {
const res = [];
let a, b;
for(let a = 1; a <= Math.sqrt(num); a++){
if(Number.isInteger(b = num/a)){
if(Number.isInteger(x = (b+a)/2)){
if(Number.isInteger(y = (b-a)/4)){
res.push([x, y]);
};
};
};
};
return res;
};
console.log(findSolution(num));
출력 결과
[ [ 45003, 22501 ], [ 9003, 4499 ], [ 981, 467 ], [ 309, 37 ] ]
코드 동작 원리
위 코드의 실행 흐름을 단계별로 살펴보면 다음과 같습니다.
- 결과를 저장할 빈 배열
res를 초기화합니다. - 1부터 √num까지 반복하면서 num의 약수 후보 a를 하나씩 검사합니다.
b = num/a가 정수인지 확인하여 a가 실제 약수인지 판별합니다.x = (b + a)/2와y = (b − a)/4가 모두 정수일 경우에만 해당 [x, y] 쌍을 결과 배열에 추가합니다.- 모든 약수에 대한 검사가 끝나면 결과 배열을 반환합니다.
이처럼 인수분해 성질을 활용하면 방정식의 구조를 단순화할 수 있으며, 약수 탐색만으로 모든 정수 해를 빠르게 찾을 수 있습니다.