JavaScript로 두 완전제곱수의 합으로 표현 가능한지 확인하는 방법

완전제곱수란?

수학에서 어떤 자연수를 제곱하여 얻을 수 있는 수를 완전제곱수(perfect square)라고 합니다.

예를 들어 9, 16, 81, 289는 모두 완전제곱수입니다. 각각 3², 4², 9², 17²에 해당합니다.

문제 정의

자연수 num을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 다음 조건을 만족하는 두 수 m과 n이 존재하는지 판별해야 합니다.

(m * m) + (n * n) = num

만약 그런 두 수가 존재한다면 함수는 true를 반환하고, 존재하지 않으면 false를 반환해야 합니다.

예시

입력 숫자가 다음과 같다면,

const num = 389;

출력 결과는 다음과 같아야 합니다.

const output = true;

그 이유는 389 = (17 × 17) + (10 × 10)으로 두 완전제곱수의 합으로 표현할 수 있기 때문입니다.

접근 방법: 투 포인터 기법

이 문제는 투 포인터(two pointer) 기법을 사용하면 효율적으로 해결할 수 있습니다. 한 포인터(left)는 0에서 시작하고, 다른 포인터(right)는 num의 제곱근을 내림한 값에서 시작합니다.

두 포인터 값의 제곱의 합이 num보다 작으면 왼쪽 포인터를 증가시키고, 합이 num보다 크면 오른쪽 포인터를 감소시킵니다. 합이 정확히 num과 같으면 조건을 만족하는 두 수를 찾은 것이므로 true를 반환합니다.

이 방법의 시간 복잡도는 O(√num)으로, 모든 조합을 일일이 검사하는 것보다 훨씬 효율적입니다.

구현 코드

const num = 389;
const canSumSquares = (num = 2) => {
    let left = 0, right = Math.floor(Math.sqrt(num));
    while(left <= right){
      if (left * left + right * right === num) {
          return true;
      } else if (left * left + right * right < num) {
          left++;
      } else {
          right--;
      };
    };
    return false;
};
console.log(canSumSquares(num));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true